Teaching Kids Programming – Find N Unique Integers Sum up to Zero

Teaching Kids Programming: Videos on Data Structures and Algorithms

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

Hints:
Return an array where the values are symmetric. (+x , -x).
If n is odd, append value 0 in your returned array.

Construct the Array by using Pairs of Integers

We can construct such array by using pairs of (+x, -x), and if it is odd number, we need an extra zero:

1
2
3
4
5
6
7
8
9
10
11
12

class Solution:
    def sumZero(self, n: int) -> List[int]:
        i = 1
        ans = []
        while n >= 2:
            ans.append(i)
            ans.append(-i)
            i += 1
            n -= 2
        if n == 1:
            ans.append(0)
        return ans

class Solution:
    def sumZero(self, n: int) -> List[int]:
        i = 1
        ans = []
        while n >= 2:
            ans.append(i)
            ans.append(-i)
            i += 1
            n -= 2
        if n == 1:
            ans.append(0)
        return ans

O(N) time and O(N) space.

Construct the Array by Sum of First N-1 Integers

We can use the first N-1 integers, and then compute its sum, and add the last number as -S. This algorithm ensures all unique numbers, and sum to zero.

1
2
3
4
5
6
7
8
9
10
11
12

class Solution:
    def sumZero(self, n: int) -> List[int]:
        i = 1
        ans = []
        s = 0
        while n > 1:
            ans.append(i)
            s += i
            i += 1
            n -= 1
        ans.append(-s)
        return ans

class Solution:
    def sumZero(self, n: int) -> List[int]:
        i = 1
        ans = []
        s = 0
        while n > 1:
            ans.append(i)
            s += i
            i += 1
            n -= 1
        ans.append(-s)
        return ans

This algorithm also works at O(N) time and O(N) space.

–EOF (The Ultimate Computing & Technology Blog) —