Microsoft OA Unique Integers That Sum Up To 0

For “Unique Integers That Sum Up To 0” and “Find N Unique Integers Sum up to Zero” problem we have two different set of input and output so please be careful while reading through the article, this questions were also asked in Microsoft Online Assessment. Make sure you scroll till the end to see both the questions.

Also See: Microsoft Online Assessment Questions and Solution

Microsoft OA Unique Integers That Sum Up To 0

Given an integer n, return any array containing n unique integers such that they add up to 0.

Example 1:

Input:5

Output: [-4,-2,0,2,4]

Example 2:

Input:3

Output: [-2, 0, 2]

Example 3:

Input:1

Output: [0]

Solution:

Program Python:

from typing import List
def numsum(n):
    res = []
    for i in range(n):
        res.append(i * 2 - n + 1)
    return res

n = int(input())
res = numsum(n)
print(' '.join(map(str, res)))

Program Java:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;
import java.util.stream.Collectors;
class Solution {
    public static List<Integer> uniqueSum(int n) {
        
        ArrayList<Integer> res = new ArrayList<>();
      
        for (int i = 0; i < n; i++) {
            res.add(i * 2 - n + 1);
        }
        return res;
    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = Integer.parseInt(scanner.nextLine());
        scanner.close();
        List<Integer> res = uniqueSum(n);
        System.out.println(res.stream().map(String::valueOf).collect(Collectors.joining(" ")));
    }
}

Now, let’s see the second questions with different input and output.

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:

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.

Program C++:

#include <iostream>
#include <vector>

using namespace std;

/*
Simple idea
n = 1, [0]
n = 2, [-1, 1]
Now write more based on this
n = 3, [-2, 0, 2]
n = 4, [-3, -1, 1, 3]
n = 5, [-4, -2, 0, 2, 4]
*/

vector<int> sumZero1(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
Find 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
*/

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

int main() {

    cout << "" << endl;

    return 0;
}

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;
}

It’s better to remember the first approach, as it’s easier to understand.

Program Python:

Using the Gauss Sum formula (n * (n + 1)) / 2 you can easily sum up all the values from 1 to n.
Concatenate the negation of the Gauss Sum for n – 1 with the range of numbers from 1 to n – 1 and you get the result.

class Solution:
    def sumZero(self, n: int) -> List[int]:
        return [- (n * (n - 1)) // 2] + list(range(1, n))

Program Java:

class Solution {
    public int[] sumZero(int n) {
        int[] ans  = new int[n];
        int num = n/2;
        int index = 0;
        while(num>0)
        {
            ans[index++] = num;
            ans[index++] = num*-1;
            num--;
        }
        if(n%2 == 1)
            ans[index++] = 0;
        return ans;
        
    }
}

Also See: AMCAT Study Materials, Preparation Guide

Also See: Amazon OA Online Assessment 2021 Questions and Answers

Microsoft Online Assessment 2021 Questions

Leave a Comment