Minimum number of working days required to achieve each of the given scores | C ++ program for the above approach ; 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 ; 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 ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int binarySeach ( vector < int > P , int N ) { int i = 0 ; int j = P . size ( ) - 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 ; } void minDays ( vector < int > P , vector < int > arr ) { for ( int i = 1 ; i < P . size ( ) ; i ++ ) { P [ i ] += P [ i ] + P [ i - 1 ] ; } for ( int i = 0 ; i < arr . size ( ) ; i ++ ) { int index = binarySeach ( P , arr [ i ] ) ; if ( index != -1 ) { cout << index + 1 << " ▁ " ; } else { cout << -1 << " ▁ " ; } } } int main ( ) { vector < int > arr = { 400 , 200 , 700 , 900 , 1400 } ; vector < int > P = { 100 , 300 , 400 , 500 , 600 } ; minDays ( P , arr ) ; return 0 ; }