Leetcode 1304. Find N Unique Integers Sum up to Zero
Problem Explanation
The problem is asking to generate n
unique integers such that their sum is equal to zero. There are many possible solutions to this problem as there are infinite ways to arrange n
numbers to sum up to zero. For example, if n
is even, you can generate the first n/2
as negative numbers and the next n/2
as positive numbers such that their absolute values are the same.
But if n
is odd, you can generate the first n/2
as negative numbers, the next n/2
as positive numbers, and the last number as zero. The sum of all these numbers will be zero and all the numbers are unique.
Consider an example where n
= 5. Some possible array configurations that meet the requirements could be [-2, -1, 0, 1, 2] or [-3, -1, 0, 2, 3]. All the integers in these arrays are unique and they all sum up to 0.
Solution Approach
The approach to the solution is to generate the numbers from -n/2
to n/2
excluding zero when n
is even and including zero when n
is odd. We achieve this by following the equation i*2 - n + 1
. This equation makes sure the sum of the generated numbers is always zero.
Step-by-step analysis
Consider n
= 5:
-
Start from i=0 to i=n.
-
For each i generate a number that is
i*2 - n + 1
. -
Here's how it looks like:
1 2 3i : 0, number : 0*2 - 5 + 1 = -4 4i : 1, number : 1*2 - 5 + 1 = -2 5i : 2, number : 2*2 - 5 + 1 = 0 6i : 3, number : 3*2 - 5 + 1 = 2 7i : 4, number : 4*2 - 5 + 1 = 4
- Store each generated number: [-4, -2, 0, 2, 4]. This array sums up to 0.
Solution
Python
1 2python 3class Solution: 4 def sumZero(self, n: int) -> List[int]: 5 return [i * 2 - n + 1 for i in range(n)]
Java
1 2java 3class Solution { 4 public int[] sumZero(int n) { 5 int[] result = new int[n]; 6 for (int i = 0; i < n; i++) { 7 result[i] = i * 2 - n + 1; 8 } 9 return result; 10 } 11}
JavaScript
1 2javascript 3var sumZero = function(n) { 4 let result = []; 5 for(let i=0; i<n; i++) { 6 result.push(i * 2 - n + 1); 7 } 8 return result; 9};
C++
1
2c++
3class Solution {
4public:
5 vector<int> sumZero(int n) {
6 vector<int> result(n);
7 for (int i = 0; i < n; i++) {
8 result[i] = i * 2 - n + 1;
9 }
10 return result;
11 }
12};
C#
1
2csharp
3public class Solution {
4 public int[] SumZero(int n) {
5 int[] result = new int[n];
6 for (int i = 0; i < n; i++) {
7 result[i] = i * 2 - n + 1;
8 }
9 return result;
10 }
11}
Each of these solutions iterates over an array of size n
, computes the unique integer associated with each index, and then returns the array of integers. Thanks to this approach, the sum of the elements of the generated array is always zero.# Time and Space Complexity Analysis
Time Complexity
The time complexity of these solutions is O(n) because a loop is run n times to generate n integers that sum up to zero. In other words, the time complexity is linearly proportional to the input size of n
. Note that there are no nested loops or recursive calls involved in the logic.
Space Complexity
The space complexity of these solutions is also O(n). Although we're not using any additional data structures such as a stack, queue, or an existing array, a new array of size n
is created to store the computed integers. So, the total space required for the functioning of these programs increases linearly with the size of the input.
Other Possible Approaches
If you wish to solve the problem in a slightly different approach, you could start from -n/2
to n/2
and add each integer starting from the negative to the positive. However, you'll need to have a special case for when n
is odd. You'll add all numbers except 0
in the array and add 0
only when n
is odd.
For instance,
Python
1 2python 3class Solution: 4 def sumZero(self, n: int) -> List[int]: 5 res = list(range(1-n, n, 2)) 6 return res
Java
1 2java 3class Solution { 4 public int[] sumZero(int n) { 5 int[] result = new int[n]; 6 int start = 1 - n; 7 for(int i=0; i < n; i++, start += 2) 8 result[i] = start; 9 return result; 10 } 11}
JavaScript
1 2javascript 3var sumZero = function(n) { 4 let result = []; 5 for(let i = 1 - n; i<n; i += 2) { 6 result.push(i); 7 } 8 return result; 9};
Most of the other logical solutions to this problem would have the same time and space complexity as explained in the previous sections. Always try to stick to the solution which is simplest and easiest to understand while also meeting the problem's requirements. This way, you not only ensure the efficiency of your code but also its readability and maintainability.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.