Skip to content

1304. Find N Unique Integers Sum up to Zero

Description

Given an integer n, return any array containing n unique integers such that they add up to 0.

 

Example 1:

Input: n = 5
Output: [-7,-1,1,3,4]
Explanation: These arrays also are accepted [-5,-1,1,2,3] , [-3,-1,2,-2,4].

Example 2:

Input: n = 3
Output: [-1,0,1]

Example 3:

Input: n = 1
Output: [0]

 

Constraints:

  • 1 <= n <= 1000

Solutions

Solution 1: Construction

We can start from \(1\) and alternately add positive and negative numbers to the result array. We repeat this process \(\frac{n}{2}\) times. If \(n\) is odd, we add \(0\) to the result array at the end.

The time complexity is \(O(n)\), where \(n\) is the given integer. Ignoring the space used for the answer, the space complexity is \(O(1)\).

1
2
3
4
5
6
7
8
9
class Solution:
    def sumZero(self, n: int) -> List[int]:
        ans = []
        for i in range(n >> 1):
            ans.append(i + 1)
            ans.append(-(i + 1))
        if n & 1:
            ans.append(0)
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution {
    public int[] sumZero(int n) {
        int[] ans = new int[n];
        for (int i = 1, j = 0; i <= n / 2; ++i) {
            ans[j++] = i;
            ans[j++] = -i;
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
public:
    vector<int> sumZero(int n) {
        vector<int> ans(n);
        for (int i = 1, j = 0; i <= n / 2; ++i) {
            ans[j++] = i;
            ans[j++] = -i;
        }
        return ans;
    }
};

1
2
3
4
5
6
7
8
9
func sumZero(n int) []int {
    ans := make([]int, n)
    for i, j := 1, 0; i <= n/2; i, j = i+1, j+1 {
        ans[j] = i
        j++
        ans[j] = -i
    }
    return ans
}

1
2
3
4
5
6
7
8
function sumZero(n: number): number[] {
    const ans: number[] = Array(n).fill(0);
    for (let i = 1, j = 0; i <= n / 2; ++i) {
        ans[j++] = i;
        ans[j++] = -i;
    }
    return ans;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
impl Solution {
    pub fn sum_zero(n: i32) -> Vec<i32> {
        let mut ans = vec![0; n as usize];
        let mut j = 0;
        for i in 1..=n / 2 {
            ans[j] = i;
            j += 1;
            ans[j] = -i;
            j += 1;
        }
        ans
    }
}

Solution 2: Construction + Mathematics

We can also add all integers from \(1\) to \(n-1\) to the result array, and finally add the opposite of the sum of the first \(n-1\) integers, which is \(-\frac{n(n-1)}{2}\), to the result array.

The time complexity is \(O(n)\), where \(n\) is the given integer. Ignoring the space used for the answer, the space complexity is \(O(1)\).

1
2
3
4
5
class Solution:
    def sumZero(self, n: int) -> List[int]:
        ans = list(range(1, n))
        ans.append(-sum(ans))
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution {
    public int[] sumZero(int n) {
        int[] ans = new int[n];
        for (int i = 1; i < n; ++i) {
            ans[i] = i;
        }
        ans[0] = -(n * (n - 1) / 2);
        return ans;
    }
}

1
2
3
4
5
6
7
8
9
class Solution {
public:
    vector<int> sumZero(int n) {
        vector<int> ans(n);
        iota(ans.begin(), ans.end(), 1);
        ans[n - 1] = -(n - 1) * n / 2;
        return ans;
    }
};

1
2
3
4
5
6
7
8
func sumZero(n int) []int {
    ans := make([]int, n)
    for i := 1; i < n; i++ {
        ans[i] = i
    }
    ans[0] = -n * (n - 1) / 2
    return ans
}

1
2
3
4
5
6
7
8
function sumZero(n: number): number[] {
    const ans = new Array(n).fill(0);
    for (let i = 1; i < n; ++i) {
        ans[i] = i;
    }
    ans[0] = -((n * (n - 1)) / 2);
    return ans;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
impl Solution {
    pub fn sum_zero(n: i32) -> Vec<i32> {
        let mut ans = vec![0; n as usize];
        for i in 1..n {
            ans[i as usize] = i;
        }
        ans[0] = -(n * (n - 1) / 2);
        ans
    }
}

Comments