#1304

Easy

LeetCode Problem Workspace

Find N Unique Integers Sum up to Zero

Generate an array of n unique integers that sum to zero using a symmetric pairing strategy to ensure balance.

Problem Statement

Given an integer n, construct an array of n unique integers such that the sum of all elements equals zero. The array should leverage symmetric properties around zero to simplify the solution and ensure correctness.

Return any valid array. For example, with n = 5, an acceptable output could be [-7,-1,1,3,4], where all integers are unique and sum to zero. Your solution must handle all values 1 <= n <= 1000 efficiently.

Examples

Example 1

Input: n = 5

Output: [-7,-1,1,3,4]

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 details omitted.

Example 3

Input: n = 1

Output: [0]

Example details omitted.

Constraints

1 <= n <= 1000

Solution Approach

Use Symmetric Pairing

Generate integers from 1 to n/2 and add their negative counterparts. If n is odd, append zero to maintain uniqueness and sum balance.

Direct Construction

Initialize an empty array, loop from 1 to n//2, append i and -i. Check if n is odd, then append 0. This ensures O(n) time and O(n) space complexity.

Validation Step

Sum the array to ensure it equals zero and all elements are unique. Adjust one element if necessary, though the symmetric construction prevents most errors.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) because each element is processed once. Space complexity is O(n) for storing the result array. No sorting or extra data structures are needed, so both are linear.

What Interviewers Usually Probe

You are expected to identify the symmetry pattern quickly.
Consider edge cases like n = 1 or very large n.
Look for an O(n) solution that avoids duplicates and ensures the sum is zero.

Common Pitfalls or Variants

Common pitfalls

Forgetting to include zero when n is odd, breaking the sum requirement.
Using random numbers without symmetry, leading to incorrect sums or duplicates.
Attempting to sort or perform unnecessary checks, adding complexity without benefit.

Follow-up variants

Return n unique integers summing to a target other than zero, using similar symmetry.
Construct the array with constraints such as all positive or all negative except one element.
Find n unique integers summing to zero, but return them sorted in ascending order.

FAQ

How do you find n unique integers that sum up to zero?

Use symmetric pairing: for each integer i from 1 to n//2, include i and -i. If n is odd, add zero to maintain the sum at zero.

What is the main pattern in this problem?

The Array plus Math pattern relies on symmetry: each positive number has a corresponding negative to sum to zero efficiently.

Can the array contain zeros or duplicates?

Only zero can appear once if n is odd. All other integers must be unique to satisfy the sum requirement.

What if n = 1?

Return [0], since the single element must sum to zero and uniqueness is trivially satisfied.

How can I optimize for large n?

Direct construction with symmetric pairing is O(n) and requires only linear space, which handles n up to 1000 efficiently.

terminal

Solution

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.

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

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.

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

Continue Practicing

#1307 verbal arithmetic puzzle #1295 find numbers with even number of digits #1330 reverse subarray to maximize array value