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> //visit www.ProDeveloperTutorial.com for 450+ solved questions #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