Given three positive integers S, K, and N, the task is to find K distinct positive integers, not exceeding N and having sum equal to S. If it is not possible to find K such positive integers, print -1.
Examples:
Input: S = 15, K = 4, N = 8
Output: 1 2 4 8
Explanation:
One possible set of K such numbers is {1, 2, 3, 4} ( Since, 1 + 2 + 4 + 8 =15).
Other possible set of K numbers are {2, 3, 4, 6}, {1, 3, 4, 7}, etc.Input: S = 14, K = 5, N = 6
Output: -1
Approach: Follow the steps below to solve the problem:
- If N is less than K, then print -1.
- If S is less than the sum of first K natural numbers, i.e. (1 + 2 + … + K) or if S is greater than the sum of last K natural numbers, i.e. from N to N – K + 1, then print -1.
- Iterate from 1 and keep adding every natural number encountered in a variable, say s1, while s1 ? S. Insert all the encountered elements in an array, say nums[].
- Extract K – 1 elements from nums[] and store in another array, say answer.
- The Kth element in the array answer[] will be (s1 – s2), where s2 is the sum of the K – 1 elements present in the array answer[].
- Traverse the array answer[] in reverse and reduce all array elements to less than or equal to N.
Below is the implementation of the above approach:
C++
// C++ implementation// for the above approach#include <bits/stdc++.h>using namespace std;// Function to represent S as// the sum of K positive integers// less than or equal to Nvoid solve(int S, int K, int N){ if (K > N) { cout << "-1" << endl; return; } int max_sum = 0, min_sum = 0; for (int i = 1; i <= K; i++) { min_sum += i; max_sum += N - i + 1; } // If S can cannot be represented // as sum of K integers if (S < min_sum || S > max_sum) { cout << "-1" << endl; return; } int s1 = 0; vector<int> nums; for (int i = 1; i <= N; i++) { // If sum of first i natural // numbers exceeds S if (s1 > S) break; s1 += i; // Insert i into nums[] nums.push_back(i); } vector<int> answer; int s2 = 0; // Insert first K - 1 positive // numbers into answer[] for (int i = 0; i < K - 1; i++) { answer.push_back(nums[i]); s2 += nums[i]; } // Insert the K-th number answer.push_back(S - s2); int Max = N; // Traverse the array answer[] for (int i = answer.size() - 1; i >= 0; i--) { // If current element exceeds N if (answer[i] > Max) { int extra = answer[i] - Max; // Add the extra value to // the previous element if (i - 1 >= 0) answer[i - 1] += extra; // Reduce current element to N answer[i] = Max; Max--; } else break; } // Printing the K numbers for (auto x : answer) cout << x << " "; cout << endl;}// Driver Codeint main(){ int S = 15, K = 4, N = 8; solve(S, K, N); return 0;} |
Java
// Java implementation// for the above approachimport java.util.Vector;class GFG{// Function to represent S as// the sum of K positive integers// less than or equal to Nstatic void solve(int S, int K, int N){ if (K > N) { System.out.println("-1"); return; } int max_sum = 0, min_sum = 0; for(int i = 1; i <= K; i++) { min_sum += i; max_sum += N - i + 1; } // If S can cannot be represented // as sum of K integers if (S < min_sum || S > max_sum) { System.out.println("-1"); return; } int s1 = 0; Vector<Integer> nums = new Vector<>(); for(int i = 1; i <= N; i++) { // If sum of first i natural // numbers exceeds S if (s1 > S) break; s1 += i; // Insert i into nums[] nums.add(i); } Vector<Integer> answer = new Vector<>(); int s2 = 0; // Insert first K - 1 positive // numbers into answer[] for(int i = 0; i < K - 1; i++) { answer.add(nums.get(i)); s2 += nums.get(i); } // Insert the K-th number answer.add(S - s2); int Max = N; // Traverse the array answer[] for(int i = answer.size() - 1; i >= 0; i--) { // If current element exceeds N if (answer.get(i) > Max) { int extra = answer.get(i) - Max; // Add the extra value to // the previous element if (i - 1 >= 0) answer.set(i - 1, answer.get(i - 1) + extra); // Reduce current element to N answer.set(i, Max); Max--; } else break; } // Printing the K numbers for(int x : answer) System.out.print(x + " "); System.out.println();}// Driver codepublic static void main(String[] args){ int S = 15, K = 4, N = 8; solve(S, K, N);}}// This code is contributed by abhinavjain194 |
Python3
# Python3 implementation# for the above approach# Function to represent S as# the sum of K positive integers# less than or equal to Ndef solve(S, K, N): if (K > N): print("-1") return max_sum, min_sum = 0, 0 for i in range(K + 1): min_sum += i max_sum += N - i + 1 # If S can cannot be represented # as sum of K integers if (S < min_sum or S > max_sum): print("-1") return s1 = 0 nums = [] for i in range(1, N + 1): # If sum of first i natural # numbers exceeds S if (s1 > S): break s1 += i # Insert i into nums[] nums.append(i) answer = [] s2 = 0 # Insert first K - 1 positive # numbers into answer[] for i in range(K - 1): answer.append(nums[i]) s2 += nums[i] # Insert the K-th number answer.append(S - s2) Max = N # Traverse the array answer[] for i in range(len(answer)-1,-1,-1): # If current element exceeds N if (answer[i] > Max): extra = answer[i] - Max # Add the extra value to # the previous element if (i - 1 >= 0): answer[i - 1] += extra # Reduce current element to N answer[i] = Max Max -= 1 else: break # Printing the K numbers for x in answer: print(x, end = " ")# Driver Codeif __name__ == '__main__': S,K,N = 15, 4, 8 solve(S, K, N)# This code is contributed by mohit kumar 29. |
C#
// C# implementation// for the above approachusing System;using System.Collections.Generic;class GFG{ // Function to represent S as// the sum of K positive integers// less than or equal to Nstatic void solve(int S, int K, int N){ if (K > N) { Console.WriteLine("-1"); return; } int max_sum = 0, min_sum = 0; for(int i = 1; i <= K; i++) { min_sum += i; max_sum += N - i + 1; } // If S can cannot be represented // as sum of K integers if (S < min_sum || S > max_sum) { Console.WriteLine("-1"); return; } int s1 = 0; List<int> nums = new List<int>(); for(int i = 1; i <= N; i++) { // If sum of first i natural // numbers exceeds S if (s1 > S) break; s1 += i; // Insert i into nums[] nums.Add(i); } List<int> answer = new List<int>(); int s2 = 0; // Insert first K - 1 positive // numbers into answer[] for(int i = 0; i < K - 1; i++) { answer.Add(nums[i]); s2 += nums[i]; } // Insert the K-th number answer.Add(S - s2); int Max = N; // Traverse the array answer[] for(int i = answer.Count - 1; i >= 0; i--) { // If current element exceeds N if (answer[i] > Max) { int extra = answer[i] - Max; // Add the extra value to // the previous element if (i - 1 >= 0) answer[i - 1] += extra; // Reduce current element to N answer[i] = Max; Max--; } else break; } // Printing the K numbers foreach(int x in answer) Console.Write(x + " "); Console.WriteLine();}// Driver Codepublic static void Main(){ int S = 15, K = 4, N = 8; solve(S, K, N);}}// This code is contributed by ukasp |
Javascript
<script>// Javascript implementation// for the above approach// Function to represent S as// the sum of K positive integers// less than or equal to Nfunction solve(S, K, N){ if (K > N) { document.write("-1"); return; } let max_sum = 0, min_sum = 0; for(let i = 1; i <= K; i++) { min_sum += i; max_sum += N - i + 1; } // If S can cannot be represented // as sum of K integers if (S < min_sum || S > max_sum) { document.write("-1"); return; } let s1 = 0; let nums = []; for(let i = 1; i <= N; i++) { // If sum of first i natural // numbers exceeds S if (s1 > S) break; s1 += i; // Insert i into nums[] nums.push(i); } let answer = []; let s2 = 0; // Insert first K - 1 positive // numbers into answer[] for(let i = 0; i < K - 1; i++) { answer.push(nums[i]); s2 += nums[i]; } // Insert the K-th number answer.push(S - s2); let Max = N; // Traverse the array answer[] for(let i = answer.length - 1; i >= 0; i--) { // If current element exceeds N if (answer[i] > Max) { let extra = answer[i] - Max; // Add the extra value to // the previous element if (i - 1 >= 0) answer[i - 1] += extra; // Reduce current element to N answer[i] = Max; Max--; } else break; } // Printing the K numbers for(let x in answer) document.write(answer[x] + " "); document.write("<br/>");} // Driver Code let S = 15, K = 4, N = 8; solve(S, K, N); // This code is contributed by susmitakundugoaldanga.</script> |
Output:
1 2 4 8
Time Complexity: O(N)
Auxiliary Space: O(N)
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!
