N Distinct Integers With Zero Sum

Easy
0/40
profile
Contributed by
1 upvote
Asked in company
Microsoft

Problem statement

You are given an integer ‘N’. Find ‘N’ distinct integers such that their sum is equal to 0.

Each selected integer should have its absolute value less than equal to 105, ie: ( -105 <= arr[i] <= 105 ). If there can be multiple possible outputs, find any of them.

Custom Test Case:

If you are running a custom test case, then 1 will be printed if the returned array is correct, else 0 will be printed.

If you wish to check your output then use print statements before returning the final answer.
Example : 
If N = 5, then the answer can be { 1, -2, 3, -6, 4 }, as: 1 + ( -2 ) + 3 + ( -6 ) + 4 = 0.

Note that { 1, -3, 5, -2, -1 } is also a valid answer for N = 5.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains a single integer ‘T’ denoting the number of test cases, then each test case follows:

The first and only line of each test case contains a single integer ‘N’ denoting the number of distinct digits to be selected.
Output Format : 
For each test case, print the N elements that sum up to 0.

Output for each test case will be printed in a separate line.
Note : 
You are not required to print anything; it has already been taken care of. Just implement the function.
Constraints : 
1 <= T <= 10      
1 <= N <= 10000

Time limit: 1 sec
Sample Input 1 :
2
5
1
Sample Output 1 :
1 -2 3 -6 4
0
Explanation For Sample Input 1 :
For test case 1 :
1 + ( -2 ) + 3 + ( -6 ) + 4 = 0

For test case 2 :
We have to select only a single integer that sums up to 0, integer ‘0’ is the only possible answer for this case.
Sample Input 2 :
2
3
2
Sample Output 2 :
1 -6 5
5 -5
Hint

The best way to compensate +x is by also including -x.

Approaches (1)
Symmetry

For N = 1, return { 0 }

For N = 2, return { -1, 1}

For N = 3, return { -1, 0, -1}

For N = 4, return { -2, -1, 1, 2}

For N = 5, return { -2, -1, 0, 1, 2} and so on…

 

Notice that we can just include elements from 1 to N / 2 and elements from -1 to -N / 2. And if the given N is odd we should also include 0.


The steps are as follows :

 

  • Initialize “ans” array to store all the N integers.
  • Run a loop for i from 1 to N / 2, and insert +i and -i in the array for each iteration.
  • Check if N is odd, and insert 0 in the ans array.
  • Finally, return the ans array.
Time Complexity

O( N ), where N is the number of distinct elements to be selected.


We are iterating from 1 to N/2 and inserting a total of N elements into the array.

Hence the time complexity is O( N ).

Space Complexity

O( N ), where N is the number of distinct elements to be selected.


We are iterating from 1 to N/2 and inserting a total of N elements into the array.

Hence the time complexity is O( N ).

Code Solution
(100% EXP penalty)
N Distinct Integers With Zero Sum
Full screen
Console