Unique Integers That Sum Up To 0 Microsoft OA 2023

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.

Unique Integers That Sum Up To 0 Solution

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]

Also See: Amazon OA Online Assessment 2023 Questions and Answers

SOLUTION

Program: Unique Integers That Sum Up To 0 Solution in 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: Unique Integers That Sum Up To 0 Solution in 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 Solution

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: Find N Unique Integers Sum up to Zero Solution in 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: Find N Unique Integers Sum up to Zero Solution in 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: Find N Unique Integers Sum up to Zero Solution in 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;
        
    }
}

Microsoft Online Assessment 2023 Questions List

Leave a Comment

twelve + 16 =