Find K positive integers not exceeding N and having sum S | C ++ implementation for the above approach ; Function to represent S as the sum of K positive integers less than or equal to N ; If S can cannot be represented as sum of K integers ; If sum of first i natural numbers exceeds S ; Insert i into nums [ ] ; Insert first K - 1 positive numbers into answer [ ] ; Insert the K - th number ; Traverse the array answer [ ] ; If current element exceeds N ; Add the extra value to the previous element ; Reduce current element to N ; Printing the K numbers ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; void 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 < min_sum S > max_sum ) { cout << " - 1" << endl ; return ; } int s1 = 0 ; vector < int > nums ; for ( int i = 1 ; i <= N ; i ++ ) { if ( s1 > S ) break ; s1 += i ; nums . push_back ( i ) ; } vector < int > answer ; int s2 = 0 ; for ( int i = 0 ; i < K - 1 ; i ++ ) { answer . push_back ( nums [ i ] ) ; s2 += nums [ i ] ; } answer . push_back ( S - s2 ) ; int Max = N ; for ( int i = answer . size ( ) - 1 ; i >= 0 ; i -- ) { if ( answer [ i ] > Max ) { int extra = answer [ i ] - Max ; if ( i - 1 >= 0 ) answer [ i - 1 ] += extra ; answer [ i ] = Max ; Max -- ; } else break ; } for ( auto x : answer ) cout << x << " ▁ " ; cout << endl ; } int main ( ) { int S = 15 , K = 4 , N = 8 ; solve ( S , K , N ) ; return 0 ; }