Minimum number of working days required to achieve each of the given scores | Java program for the above approach ; 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
public class GFG { static void minDays ( int [ ] P , int [ ] arr ) { for ( int i = 1 ; i < P . length ; i ++ ) { P [ i ] += P [ i ] + P [ i - 1 ] ; } for ( int i = 0 ; i < arr . length ; i ++ ) { int index = binarySeach ( P , arr [ i ] ) ; if ( index != - 1 ) { System . out . print ( index + 1 + " ▁ " ) ; } else { System . out . print ( - 1 + " ▁ " ) ; } } } static int binarySeach ( int [ ] P , int N ) { int i = 0 ; int j = P . length - 1 ; int index = - 1 ; while ( i <= j ) { int mid = i + ( j - i ) / 2 ; if ( P [ mid ] >= N ) { index = mid ; j = mid - 1 ; } else { i = mid + 1 ; } } return index ; } public static void main ( String [ ] args ) { int [ ] arr = { 400 , 200 , 700 , 900 , 1400 } ; int [ ] P = { 100 , 300 , 400 , 500 , 600 } ; minDays ( P , arr ) ; } }