{x}
blog image

Find N Unique Integers Sum up to Zero

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

Solution Explanation for LeetCode 1304: Find N Unique Integers Sum up to Zero

This problem asks to generate an array of n unique integers that sum up to zero. There are several approaches to solve this, and we'll explore two efficient methods.

Approach 1: Pairing Positive and Negative Numbers

This approach is intuitive and efficient. We generate pairs of positive and negative integers, ensuring uniqueness. If n is odd, we add a zero to the array.

Algorithm:

  1. Handle even n: If n is even, create pairs of numbers from 1 to n/2. The first number in the pair is the positive number, and the second is its negative counterpart. Add these pairs to the result array.
  2. Handle odd n: If n is odd, follow step 1 and then add 0 to the result array.

Time Complexity: O(n) - We iterate through the numbers once. Space Complexity: O(n) - We store the array of size n.

Code Implementation:

(The code examples are already provided in the original prompt, this section just clarifies the logic behind the code)

The Python, Java, C++, Go, and TypeScript code examples all follow the same logic. They use a loop that iterates up to n/2. In each iteration, a positive number i and its negative counterpart -i are added to the result array. If n is odd, they add 0 to the end.

Approach 2: Using the Sum of Arithmetic Series

This approach leverages the formula for the sum of an arithmetic series. We generate numbers from 1 to n-1 and then calculate the last number such that the sum of all numbers is 0.

Algorithm:

  1. Generate numbers: Create an array with numbers from 1 to n-1.
  2. Calculate the last number: The sum of numbers from 1 to n-1 is (n-1) * n / 2. The last number should be the negative of this sum to make the total sum zero. Add this number to the end of the array.

Time Complexity: O(n) - The loop to generate numbers takes O(n) time. Space Complexity: O(n) - We store the array of size n.

Code Implementation:

(Again, code is in the original response. This section just describes the logic.)

The code in all languages first creates an array with numbers from 1 to n-1. It then calculates the sum of this arithmetic series using the formula (n - 1) * n / 2 and negates it to obtain the last element of the array. This negative sum is then added to the end, ensuring that all numbers sum up to zero.

Comparison of Approaches:

Both approaches have the same time and space complexity. Approach 1 is arguably more intuitive and easier to understand, while Approach 2 demonstrates a more mathematical approach. The choice depends on personal preference and coding style. Approach 1 is generally preferred for its simplicity and readability.