Minimum count of indices to be skipped for every index of Array to keep sum till that index at most T | 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
def skipIndices ( N , T , arr ) : NEW_LINE INDENT sum = 0 NEW_LINE count = { } NEW_LINE for i in range ( N ) : NEW_LINE INDENT d = sum + arr [ i ] - T NEW_LINE k = 0 NEW_LINE if ( d > 0 ) : NEW_LINE INDENT for u in list ( count . keys ( ) ) [ : : - 1 ] : NEW_LINE INDENT j = u NEW_LINE x = j * count [ j ] NEW_LINE if ( d <= x ) : NEW_LINE INDENT k += ( d + j - 1 ) // j NEW_LINE break NEW_LINE DEDENT k += count [ j ] NEW_LINE d -= x NEW_LINE DEDENT DEDENT sum += arr [ i ] NEW_LINE count [ arr [ i ] ] = count . get ( arr [ i ] , 0 ) + 1 NEW_LINE print ( k , end = " ▁ " ) NEW_LINE DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT N = 7 NEW_LINE T = 15 NEW_LINE arr = [ 1 , 2 , 3 , 4 , 5 , 6 , 7 ] NEW_LINE skipIndices ( N , T , arr ) NEW_LINE DEDENT