Arrays: Find unique numbers that sum upto zero

Problem Statement:

You are given an integer n. You need to return the integers that sum upto 0.

Example

Input: n = 5
Output: {-5, -1, 1, 2, 3}

Solution

Method 1:

In this method, we will use the numbers from 1, 2, .. n-1 and then negation.

Method 2:

Consider the cases below

n = 1, [0]
n = 2, [-1, 1]
n = 3, [-2, 0, 2]
n = 4, [-3, -1, 1, 3]
n = 5, [-4, -2, 0, 2, 4]

So we can derive mathematical formula as : A[i] = i * 2 – n + 1

Solution in C++

#include <algorithm>  
#include <iostream>    
#include <string>
#include <stack>
#include <vector>
#include <unordered_map> 
#include <queue> 

using namespace std;

vector<int> sum_zero_method_1(int n) 
{
    vector<int> a(n);
    for (int i = 1; i < n; i++) 
    {
        a[i] = i;
        a[0] -= i;
    }
    return a;
}

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

int main()
{
  int n = 5;

  vector<int> result = sum_zero_method_1(n);

  cout<<"The solution using 1st method = ";

  for(int i = 0; i<result.size(); i++)
  {
    cout<<result[i]<<" ";
  }
  cout<<endl;

  result = sum_zero_method_2(n);
  cout<<"The solution using 2nd method = ";

  for(int i = 0; i<result.size(); i++)
  {
    cout<<result[i]<<" ";
  }
  cout<<endl;
}

Output:

The solution using 1st method = -10 1 2 3 4
The solution using 2nd method = -4 -2 0 2 4