Minimum count of elements to be inserted in Array to form all values in [ 1 , K ] using subset sum | C ++ program for the above approach ; Function to find the count of minimum elements to be inserted to form every number in a range ; Stores the count of numbers needed ; Stores the numbers upto which every numbers can be formed ; Stores the index of the array arr [ ] ; Iterate until requiredSum is less than or equal to K ; If i is less than N and requiredSum is greater than or equal to arr [ i ] ; Increment requiredSum by arr [ i ] ; Increment i by 1 ; Otherwise ; Increment count by 1 ; Increment requiredSum by requiredSum ; Return result ; Driver Code ; Input ; Function Call
#include <iostream> NEW_LINE using namespace std ; int minElements ( int arr [ ] , int N , int K ) { int count = 0 ; long long requiredNum = 1 ; int i = 0 ; while ( requiredNum <= K ) { if ( i < N && requiredNum >= arr [ i ] ) { requiredNum += arr [ i ] ; i ++ ; } else { count ++ ; requiredNum += requiredNum ; } } return count ; } int main ( ) { int arr [ ] = { 1 , 3 } ; int K = 6 ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cout << minElements ( arr , N , K ) << endl ; return 0 ; }