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

Description:

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:

[-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.

--

--

Looking for an interesting project to join. https://www.linkedin.com/in/molchevsky/

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store