Find N Unique Integers Sum up to Zero

EASY

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

Approaches

Checkout 2 different approaches to solve Find N Unique Integers Sum up to Zero. Click on different approaches to view the approach and algorithm in detail.

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.

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.

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.

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

Complexity Analysis

Time Complexity: 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 Complexity: 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 and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Find N Unique Integers Sum up to Zero. Click on different languages to view the code.

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

Video Solution

Watch the video walkthrough for Find N Unique Integers Sum up to Zero

Patterns:

Math

Data Structures:

Array