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.
Contents
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
- Maximal Network Rank Solution
- Min Deletions To Obtain String in Right Format
- Day of week that is K days later Solution
- Minimum Adjacent Swaps to Make Palindrome Solution
- Lexicographically Smallest String
- Longest Substring Without Two Contiguous Occurrences of Letter
- String Without 3 Identical Consecutive Letters
- Microsoft OA Longest Semi-Alternating Substring
- Microsoft OA Min Steps to Make Piles Equal Height
- Max Inserts to Obtain String Without 3 Consecutive ‘a’
- Concatenated String Length with unique Characters
- Largest K such that both K and -K exist in array
- Microsoft OA Min Adj Swaps to Group Red Balls
- Maximum Length of a Concatenated String with Unique Characters
- Microsoft OA Unique Integers That Sum Up To 0
- Find N Unique Integers Sum up to Zero
- Microsoft OA Particle Velocity Solution
- Microsoft OA Arithmetic Slices Solution
- Microsoft OA Widest Path Without Trees Solution
- Microsoft OA Jump Game Solution
- Microsoft OA Fair Indexes Solution