Find N Unique Integers Sum up to Zero Leetcode Solution

Difficulty Level Easy
Frequently asked in Adobe Amazon Facebook Microsoft
algorithms Array coding Interview interviewprep LeetCode LeetCodeSolutionsViews 4692

The problem Find N Unique Integers Sum up to Zero Leetcode Solution, provides us with an integer. It asks us to return n unique integers that sum up to 0. So, the question is pretty simple to understand. So, before diving into the solution. Let us take a look at a few examples.

Find N Unique Integers Sum up to Zero Leetcode Solution

n = 5
[-7,-1,1,3,4]

Explanation: Well, there can be multiple outputs to the problem. But let us take the given output. All the integers in the output are unique. Thus satisfying the imposed condition and the sum of all the given integers is 0. Hence, both the conditions are satisfied.

n = 3
[-1, 0, 1]

Explanation: The output given has all unique integers and their sum is also 0. Thus, the output satisfies all the imposed conditions.

Approach for Find N Unique Integers Sum up to Zero Leetcode Solution

The approach for the problems is most of the times is cracking the pattern. There is always some underlying patterns in these type of questions. So, whenever we try to find the pattern for a question. Always try to find the answer for smaller values of n, then try to find the pattern. For n = 1, output can be 0. For n = 2, output can be [-1, 1]. Similarly for n = 3, output can be [-2, 0, 2], for n = 4, output can be [-3, -1, 1, 3]. So, we see a pattern that the output forms AP where if the value of n is odd. The middle element is 0. If the value of n is even then the (n+1)/2 element is 1. So, using this information, we can devise a formula. The formula can be a[i] = 2*i+1-n. Now, we simply use this formula to fill the n elements of the array.

Code to Find N Unique Integers Sum up to Zero Leetcode Solution

C++ code

#include <bits/stdc++.h>
using namespace std;

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

int main(){
    vector<int> output = sumZero(7);
    for(auto x: output)
        cout<<x<<" ";
}

-6 -4 -2 0 2 4 6

Java code

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
    public static int[] sumZero(int n) {
        int[] v = new int[n];
        for(int i=0;i<n;i++)
            v[i]= 2*i - n + 1;
        return v;
    }
    
    public static void main(String[] args){
    	int[] output = sumZero(7);
    	for(int i=0;i<7;i++)
    		System.out.print(output[i]+" ");
    }
}
-6 -4 -2 0 2 4 6

Complexity Analysis

Time Complexity

O(N), since we simply fill the array and each element can be calculated in O(1). Thus, the time complexity is linear.

Space Complexity

O(N), because we create an array that has to be returned as output.

Translate »