# Find N Unique Integers Sum up to Zero
**Difficulty:** EASY
[External](https://leetcode.com/problems/find-n-unique-integers-sum-up-to-zero)
Canonical: https://scaleengineer.com/dsa/problems/find-n-unique-integers-sum-up-to-zero
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
**Data structures:** Array
---
## Problem
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`

# Approaches
## Iterative Construction with Sum Tracking
This approach involves building the array by adding `n-1` unique integers and then calculating the final integer needed to make the sum of the array zero. For instance, we can add the integers `1, 2, ..., n-1`.
**Time:** O(n) - We iterate once through the first `n-1` elements of the array to populate them. This is a single loop that runs `n-1` times, resulting in a linear time complexity. · **Space:** O(n) or O(1) - We need an array of size `n` to store and return the result. If the space for the output array is considered, the complexity is O(n). If not, the extra space used is O(1) for the sum variable.
**Pros:** Conceptually simple and easy to implement.; Guaranteed to produce a correct and valid result for any `n >= 1`.
**Cons:** The magnitude of the last number can be quite large. The sum of the first `k` integers is `k*(k+1)/2`. For `n=1000`, the last number would be `-(999*1000)/2 = -499500`.; Slightly less elegant compared to the symmetric approach.
### Explanation
The core idea is to fill the first `n-1` positions of the result array with simple, unique integers. A straightforward choice is to use the sequence `1, 2, 3, ..., n-1`. While filling the array, we keep track of the sum of these numbers. After placing `n-1` numbers, the sum will be `S = 1 + 2 + ... + (n-1)`. To make the total sum of all `n` integers zero, the last integer must be `-S`. This guarantees the sum-to-zero property. We also need to ensure all `n` integers are unique. Since we added positive integers `1` through `n-1`, the final number `-S` will be negative (for `n > 1`) and thus distinct from the others. For the base case `n=1`, the loop is skipped, the sum is 0, and the result is `[0]`, which is correct.

```java
class Solution {
    public int[] sumZero(int n) {
        int[] result = new int[n];
        int currentSum = 0;
        for (int i = 0; i < n - 1; i++) {
            result[i] = i + 1;
            currentSum += result[i];
        }
        if (n > 0) { // To handle n=0 case if constraints allowed, though here n>=1
            result[n - 1] = -currentSum;
        }
        return result;
    }
}
```
### Algorithm
- Create an integer array `result` of size `n`.
- Initialize a variable `currentSum` to 0.
- Iterate from `i = 0` to `n-2`:
  - Set `result[i] = i + 1`.
  - Add `i + 1` to `currentSum`.
- Set the last element of the array, `result[n-1]`, to `-currentSum`.
- Return the `result` array.

## Symmetric Pair Construction
A more elegant and efficient approach is to construct the array using symmetric pairs of integers (+x, -x). This naturally keeps the running sum at zero. If `n` is odd, a single zero is added to complete the array.
**Time:** O(n) - The loop runs `n / 2` times. Inside the loop, we perform a constant number of operations (two array assignments). Therefore, the total time taken is proportional to `n`. · **Space:** O(n) or O(1) - Similar to the first approach, we require an array of size `n` for the output. The space complexity is O(n) if this is counted, and O(1) otherwise, as we only use a few variables for iteration.
**Pros:** Very elegant and intuitive.; Produces integers with the smallest possible absolute values.; Extremely simple to implement and reason about.
**Cons:** There are no significant disadvantages to this approach; it is considered optimal for this problem.
### Explanation
This method leverages a simple mathematical property: `x + (-x) = 0`. We can build the array by adding pairs of numbers `(i, -i)`. We iterate from `1` up to `n / 2`. In each step, we add both `i` and `-i` to our result array. This ensures that for every positive number added, its additive inverse is also present, keeping the cumulative sum of the array at zero. All these numbers (`1, -1, 2, -2, ...`) are unique. If `n` is even, this process fills the entire array. If `n` is odd, this process fills `n-1` spots, leaving one position empty. To complete the array without changing the sum (which is already 0), we simply add `0` to the last spot. The number `0` is unique as we only added non-zero integers previously.

```java
class Solution {
    public int[] sumZero(int n) {
        int[] result = new int[n];
        int index = 0;
        for (int i = 1; i <= n / 2; i++) {
            result[index++] = i;
            result[index++] = -i;
        }
        if (n % 2 == 1) {
            result[index] = 0;
        }
        return result;
    }
}
```
### Algorithm
- Create an integer array `result` of size `n`.
- Iterate from `i = 1` to `n / 2` (integer division).
  - Add `i` to the result array.
  - Add `-i` to the result array.
- If `n` is an odd number, add `0` to the last remaining spot in the array.
- Return the `result` array.

# Solutions
### Java

```java
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 ; } }
```

### CPP

```cpp
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 ; } };
```

### Python

```python
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
```