Code Implementation

class Solution:
    def sumZero(self, n: int) -> list[int]:
        res = []
        for i in range(1, n // 2 + 1):
            res.append(i)
            res.append(-i)
        if n % 2 == 1:
            res.append(0)
        return res
      

class Solution {
public:
    vector<int> sumZero(int n) {
        vector<int> res;
        for (int i = 1; i <= n / 2; ++i) {
            res.push_back(i);
            res.push_back(-i);
        }
        if (n % 2 == 1) {
            res.push_back(0);
        }
        return res;
    }
};
      

class Solution {
    public int[] sumZero(int n) {
        int[] res = new int[n];
        int idx = 0;
        for (int i = 1; i <= n / 2; i++) {
            res[idx++] = i;
            res[idx++] = -i;
        }
        if (n % 2 == 1) {
            res[idx] = 0;
        }
        return res;
    }
}
      

var sumZero = function(n) {
    let res = [];
    for (let i = 1; i <= Math.floor(n / 2); i++) {
        res.push(i);
        res.push(-i);
    }
    if (n % 2 === 1) {
        res.push(0);
    }
    return res;
};
      

Problem Description

You are given an integer n. Your task is to find n unique integers such that their sum is exactly zero. Each integer must be unique (no repeats), and you must return any valid array of size n that satisfies the condition.

• Each element in the result must be an integer.
• No element can be used more than once.
• There is always exactly one valid solution for each input n.
• The order of the elements in the output does not matter.

Example: For n = 5, a possible output is [-7, -1, 1, 3, 4] (since their sum is 0).

Thought Process

The main challenge is to generate n different numbers that add up to zero, with no duplicates. At first glance, you might consider brute-forcing all combinations of n numbers and checking their sum, but this would be extremely inefficient, especially for larger n.

Instead, let's think about the properties of numbers and sums. If you pair a positive and its negative (like 2 and -2), their sum is zero. So, if n is even, you can create n/2 pairs of (x, -x), and the sum is zero. If n is odd, you can create floor(n/2) pairs and add a single zero to reach the desired count and sum.

This approach is both efficient and guarantees uniqueness, since all numbers in the pairs are distinct and the zero (if used) is unique as well.

Solution Approach

Let's break down the steps to construct the solution:

1. Initialize an empty result list or array.
2. Loop from 1 to n//2:
   • For each number i in this range, add both i and -i to the result. This ensures pairs that sum to zero and are unique.
3. If n is odd:
   • Add a single 0 to the result. This brings the total count to n and does not affect the sum.
4. Return the result.

Why does this work? All numbers are unique by construction, the sum is zero (since each pair sums to zero, and the optional zero does not affect the sum), and the count is exactly n.

Example Walkthrough

Let's walk through the process with n = 5:

1. Initialize res = [].
2. Loop from 1 to 5 // 2 = 2:
• i = 1: Add 1 and -1 → res = [1, -1]
• i = 2: Add 2 and -2 → res = [1, -1, 2, -2]
3. Since 5 is odd, add 0 → res = [1, -1, 2, -2, 0]
4. Sum: 1 + (-1) + 2 + (-2) + 0 = 0
5. All numbers are unique, and the total count is 5.

Another example: n = 4

• Loop i = 1: Add 1 and -1 → res = [1, -1]
• Loop i = 2: Add 2 and -2 → res = [1, -1, 2, -2]
• n is even, so we do not add 0.
• Sum: 1 + (-1) + 2 + (-2) = 0
• All numbers are unique, and the total count is 4.

Time and Space Complexity

Brute-Force Approach: If you tried all possible combinations of n integers, the time complexity would be exponential, specifically O(Mⁿ), where M is the range of numbers you consider. This is not feasible.

Optimized Approach (Our Solution):

• Time Complexity: O(n), since we loop up to n/2 and possibly add one more element.
• Space Complexity: O(n), as we store n integers in the result.

The algorithm is efficient and works well for any reasonable value of n.

Summary

The key insight is pairing positive and negative numbers, and optionally including zero for odd n. This guarantees uniqueness, the correct count, and a sum of zero, all in linear time and space. The approach is both elegant and simple, making it ideal for this problem.