Minimum count of indices to be skipped for every index of Array to keep sum till that index at most T | C ++ approach for above approach ; Function to calculate minimum indices to be skipped so that sum till i remains smaller than T ; Store the sum of all indices before i ; Store the elements that can be skipped ; Traverse the array , A [ ] ; Store the total sum of elements that needs to be skipped ; Store the number of elements need to be removed ; Traverse from the back of map so as to take bigger elements first ; Update sum ; Update map with the current element ; Driver code ; Given Input ; Function Call
import java . util . ArrayList ; import java . util . Map ; import java . util . TreeMap ; class GFG { public static void skipIndices ( int N , int T , int arr [ ] ) { int sum = 0 ; TreeMap < Integer , Integer > count = new TreeMap < Integer , Integer > ( ) ; for ( int i = 0 ; i < N ; i ++ ) { int d = sum + arr [ i ] - T ; int k = 0 ; if ( d > 0 ) { for ( Map . Entry < Integer , Integer > u : count . descendingMap ( ) . entrySet ( ) ) { int j = u . getKey ( ) ; int x = j * count . get ( j ) ; if ( d <= x ) { k += ( d + j - 1 ) / j ; break ; } k += count . get ( j ) ; d -= x ; } } sum += arr [ i ] ; if ( count . containsKey ( arr [ i ] ) ) { count . put ( arr [ i ] , count . get ( arr [ i ] ) + 1 ) ; } else { count . put ( arr [ i ] , 1 ) ; } System . out . print ( k + " ▁ " ) ; } } public static void main ( String args [ ] ) { int N = 7 ; int T = 15 ; int arr [ ] = { 1 , 2 , 3 , 4 , 5 , 6 , 7 } ; skipIndices ( N , T , arr ) ; } }