Given an integer N, the task is to find N distinct integers whose sum is N. If there is more than one combination of the integers, print any one of them.
Examples:
Input: N = 3
Output: 1, -1, 3
Explanation:
On adding the numbers that is 1 + (-1) + 3 the sum is 3.Input: N = 4
Output: 1, -1, 0, 4
Explanation:
On adding the numbers that is 1 + (-1) + 0 + (4) the sum is 4.
Approach: The idea is to print N/2 Symmetric Pairs like (+x, -x) so that the resultant sum will always be 0.
Now if integer N is odd, then print N along with these set of integers to make sum of all integers equals to N
If N is even, print 0 and N along with these set of integers to make sum of all integers equals to N.
Below is the implementation of the above approach:
C++
// C++ for the above approach#include <bits/stdc++.h>using namespace std;// Function to print distinct N// numbers whose sum is Nvoid findNumbers(int N){ // To store how many symmetric // pairs needs to be calculated int half = N / 2; // For even N we have to print // one less symmetric pair if (N % 2 == 0) { half--; } // Iterate till [1 n/2] and Print // all symmetric pairs(i, -i) for (int i = 1; i <= half; i++) { // Print 2 symmetric numbers cout << (-1) * i << ", " << i << ", "; } // if N is Odd, then print N if (N & 1) { cout << N << endl; } // Else print(0, N) else { cout << 0 << ", " << N << endl; }}// Driver Codeint main(){ // Given Sum int N = 5; // Function Call findNumbers(N); return 0;} |
Java
// Java for the above approachclass GFG{ // Function to print distinct N // numbers whose sum is N public static void findNumbers(int N) { // To store how many symmetric // pairs needs to be calculated int half = N / 2; // For even N we have to print // one less symmetric pair if (N % 2 == 0) { half--; } // Iterate till [1 n/2] and Print // all symmetric pairs(i, -i) for(int i = 1; i <= half; i++) { // Print 2 symmetric numbers System.out.print((-1) * i + ", " + i + ", "); } // if N is Odd, then print N int check = N & 1; if (check != 0) { System.out.println(N); } // Else print(0, N) else { System.out.println(0 + ", " + N); }} // Driver codepublic static void main(String[] args){ // Given sum int N = 5; // Function sall findNumbers(N); }}// This code is contributed by divyeshrabadiya07 |
Python3
# Python3 code for the above approach # Function to print distinct N # numbers whose sum is N def findNumbers(N): # To store how many symmetric # pairs needs to be calculated half = int(N / 2) # For even N we have to print # one less symmetric pair if (N % 2 == 0): half = half - 1 # Iterate till [1 n/2] and Print # all symmetric pairs(i, -i) for i in range(1, half + 1): # Print 2 symmetric numbers print((-1) * i, end = ', ') print(i, end = ', ') # If N is Odd, then print N if (N & 1): print(N, end = '\n') # Else print(0, N) else: print(0, end = ', ') print(N, end = '\n') # Driver Code N = 5# Function Call findNumbers(N)# This code is contributed by PratikBasu |
C#
// C# for the above approachusing System;class GFG{ // Function to print distinct N // numbers whose sum is N public static void findNumbers(int N) { // To store how many symmetric // pairs needs to be calculated int half = N / 2; // For even N we have to print // one less symmetric pair if (N % 2 == 0) { half--; } // Iterate till [1 n/2] and Print // all symmetric pairs(i, -i) for(int i = 1; i <= half; i++) { // Print 2 symmetric numbers Console.Write((-1) * i + ", " + i + ", "); } // if N is Odd, then print N int check = N & 1; if (check != 0) { Console.Write(N + "\n"); } // Else print(0, N) else { Console.Write(0 + ", " + N + "\n"); }} // Driver codepublic static void Main(string[] args){ // Given sum int N = 5; // Function sall findNumbers(N); }}// This code is contributed by rutvik_56 |
Javascript
<script>// javascript program for the above approach// Function to print distinct N// numbers whose sum is Nfunction findNumbers( N){ // To store how many symmetric // pairs needs to be calculated let half = parseInt(N / 2); // For even N we have to print // one less symmetric pair if (N % 2 == 0) { half--; } // Iterate till [1 n/2] and Print // all symmetric pairs(i, -i) for (let i = 1; i <= half; i++) { // Print 2 symmetric numbers document.write( (-1) * i + ", " + i + ", "); } // if N is Odd, then print N if (N & 1) { document.write( N); } // Else print(0, N) else { document.write( 0 + ", " + N +"<br/>"); }}// Driver Code // Given Sum let N = 5; // Function Call findNumbers(N); // This code contributed by aashish1995 </script> |
Output:
-1,1,-2,2,5
Time Complexity: O(N/2) which is asymptotically same as O(N).
Space Complexity: O(1) as no extra space has been used.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
