Minimize insertions to make sum of every pair of consecutive array elements at most K | C ++ program for the above approach ; Function to count minimum number of insertions required to make sum of every pair of adjacent elements at most K ; Stores if it is possible to make sum of each pair of adjacent elements at most K ; Stores the count of insertions ; Stores the previous value to index i ; Traverse the array ; If arr [ i ] is greater than or equal to K ; Mark possible 0 ; If last + arr [ i ] is greater than K ; Increment res by 1 ; Assign arr [ i ] to last ; If possible to make the sum of pairs of adjacent elements at most K ; Otherwise print " - 1" ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; void minimumInsertions ( int arr [ ] , int N , int K ) { bool possible = 1 ; int res = 0 ; int last = 0 ; for ( int i = 0 ; i < N ; i ++ ) { if ( arr [ i ] >= K ) { possible = 0 ; break ; } if ( last + arr [ i ] > K ) res ++ ; last = arr [ i ] ; } if ( possible ) { cout << res ; } else { cout << " - 1" ; } } int main ( ) { int arr [ ] = { 1 , 2 , 3 , 4 , 5 } ; int K = 6 ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; minimumInsertions ( arr , N , K ) ; return 0 ; }