Minimum number of working days required to achieve each of the given scores | Function to find the minimum number of days required to work to at least arr [ i ] points for every array element ; Traverse the array P [ ] ; Find the prefix sum ; Traverse the array arr [ ] ; Find the minimum index of the array having value at least arr [ i ] ; If the index is not - 1 ; Otherwise ; Function to find the lower bound of N using binary search ; Stores the lower bound ; Stores the upper bound ; Stores the minimum index having value is at least N ; Iterater while i <= j ; Stores the mid index of the range [ i , j ] ; If P [ mid ] is at least N ; Update the value of mid to index ; Update the value of j ; Update the value of i ; Return the resultant index ; Driver Code
def minDays ( P , arr ) : NEW_LINE INDENT for i in range ( 1 , len ( P ) ) : NEW_LINE INDENT P [ i ] += P [ i ] + P [ i - 1 ] NEW_LINE DEDENT for i in range ( len ( arr ) ) : NEW_LINE INDENT index = binarySeach ( P , arr [ i ] ) NEW_LINE if ( index != - 1 ) : NEW_LINE INDENT print ( index + 1 , end = " ▁ " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( - 1 , end = " ▁ " ) NEW_LINE DEDENT DEDENT DEDENT def binarySeach ( P , N ) : NEW_LINE INDENT i = 0 NEW_LINE j = len ( P ) - 1 NEW_LINE index = - 1 NEW_LINE while ( i <= j ) : NEW_LINE INDENT mid = i + ( j - i ) // 2 NEW_LINE if ( P [ mid ] >= N ) : NEW_LINE INDENT index = mid NEW_LINE j = mid - 1 NEW_LINE DEDENT else : NEW_LINE INDENT i = mid + 1 NEW_LINE DEDENT DEDENT return index NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 400 , 200 , 700 , 900 , 1400 ] NEW_LINE P = [ 100 , 300 , 400 , 500 , 600 ] NEW_LINE minDays ( P , arr ) NEW_LINE DEDENT