Generate an array of K elements such that sum of elements is N and the condition a [ i ] < a [ i + 1 ] <= 2 * a [ i ] is met | Set 2 | C ++ implementation of the approach ; Function that print the desired array which satisfies the given conditions ; If the lowest filling condition is void , then it is not possible to generate the required array ; Increase all the elements by cnt ; Start filling from the back till the number is a [ i + 1 ] <= 2 * a [ i ] ; Get the number to be filled ; If it is less than the remaining numbers to be filled ; less than remaining numbers to be filled ; Get the sum of the array ; If this condition is void at any stage during filling up , then print - 1 ; Else add it to the sum ; If the sum condition is not satisified , then print - 1 ; Print the generated array ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; void solve ( int n , int k ) { int mini = 0 ; int x1 = 1 ; int a [ k ] ; for ( int i = 1 ; i <= k ; i ++ ) { mini += x1 ; a [ i - 1 ] = x1 ; x1 += 1 ; } if ( n < mini ) { cout << " - 1" ; return ; } int rem = n - mini ; int cnt = rem / k ; rem = rem % k ; for ( int i = 0 ; i < k ; i ++ ) a [ i ] += cnt ; for ( int i = k - 1 ; i > 0 && rem > 0 ; i -- ) { int xx = a [ i - 1 ] * 2 ; int left = xx - a [ i ] ; if ( rem >= left ) { a [ i ] = xx ; rem -= left ; } else { a [ i ] += rem ; rem = 0 ; } } int sum = a [ 0 ] ; for ( int i = 1 ; i < k ; i ++ ) { if ( a [ i ] > 2 * a [ i - 1 ] ) { cout << " - 1" ; return ; } sum += a [ i ] ; } if ( sum != n ) { cout << " - 1" ; return ; } for ( int i = 0 ; i < k ; i ++ ) cout << a [ i ] << " ▁ " ; } int main ( ) { int n = 26 , k = 6 ; solve ( n , k ) ; return 0 ; }