Best solutions for Microsoft interview tasks. Unique Integers That Sum Up To 0

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

Solution:

This task is very simple. We don’t need to play with a random number generator. We just need to make an array of different numbers. For example sequence 012345 contains different and unique numbers. So we just generate two the same sequences of numbers and make one of them negative. For example:

[-3, -2,-1,0,1,2,3]

All numbers of this sequence are unique and sum of them = 0. This is exactly what we need. The only thing we need to check is check if the given n is odd or even. In case n is odd we will add zero to our sequence, if n is even we will not do it.

C++ code:

vector<int> solution(int n) {
    vector<int> v;
    v.reserve(n);
    int until = n/2;
    // if n is odd
    if (n & 1) { v.push_back(0); }
    for (int i = 1; i <= until; ++i) { 
        v.push_back(i); v.push_back(-i); 
    }
    return v;
}

Another idea based on properties of the sequence. You can note that each item of the required sequence following the rule A[i] = i * 2 — n + 1

Math Observation

Actually, this rule could be derived from constructing an arithmetic sequence.

(Note that any arithmetic sequence must have unique values if the common delta is non-zero)

We need the sequence sum, so that

(a[0] + a[n-1]) * n / 2 = 0, which means a[0] + a[n-1] = 0.

Note that a[n-1] — a[0] = (n-1) * delta, which is -2 * a[0],

so we simply set delta = 2, a[0] = 1 — n

The solution code will looks like:

vector<int> solution2(int n) {
    vector<int> v(n);
    for (int i = 0; i < n; ++i) {
        v[i] = i * 2 - n + 1;
    }
    return v;
}

But IMHO if you preparing to an interview it would be much easier to remember the first approach.

Repository with the full project you can find here: https://github.com/jolly-fellow/microsoft/tree/master/unique_integers_that_sum_up_to_0

Return to the table of contents.