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

Thinking

We need \(n\) distinct integers that sum to \(0\). Picking numbers at random and then adjusting them easily breaks uniqueness. A pair of opposite numbers already sums to \(0\), so we emit \(1,-1,\ldots,k,-k\). When \(n\) is odd we append \(0\), which preserves both the sum and distinctness.

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

Thinking

Pairing must treat odd and even \(n\) separately. Placing \(1\) through \(n-1\) and appending the negation of their sum forces the total to \(0\), and that last value cannot equal any of those positive integers. The construction is shorter and still distinct.

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