Given an array arr[] consisting of N integers and an array P[] consisting of M integers such that P[i] represents the score obtained by working on the ith day. The task is to find the minimum number of days needed to work to achieve a score of at least arr[i], for each array element arr[i].
Examples:
Input: arr[] = {400, 200, 700}, P[] = {100, 300, 400, 500, 600}
Output: 2 2 3 4 5
Explanation:
Following are the number of days required for each array elements:
- arr[0](= 400): To earn 400 points one has to work for first 2 days making the total points equal to 100 + 300 = 400(>= arr[0]).
- arr[1](= 200): To earn 200 points one has to work for first 2 days making the total points = 100 + 300 = 400(>= arr[1]).
- arr[2](= 700): To earn 700 points one has to work for first 3 days making the total points = 100 + 300 + 400 = 800(>= arr[2]).
Input: arr[] = {1400}, P[] = {100, 300}
Output: -1
Naive Approach: The simplest approach to solve the problem is to traverse the array arr[] and for every array, element find the minimum index of the array P[] such that the sum of the subarray over the range [0, i] is at least arr[i].
Time Complexity: O(N2)
Auxiliary Space: O(1)
Efficient Approach: The above approach can be optimized by finding the prefix sum array of P[] and then using binary search to find the sum whose value is at least arr[i]. Follow the steps below to solve the problem:
- Find the prefix sum array of the array P[].
- Traverse the given array arr[] and perform the following steps:
- Find the index of the first element greater than the current element arr[i] in the array P[] and store it in a variable, say index.
- If the value of the index is -1, then print -1. Otherwise, print the value of the (index + 1) as the result for the current index.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the lower bound // of N using binary search int binarySeach(vector< int > P, int N) { // Stores the lower bound int i = 0; // Stores the upper bound int j = P.size() - 1; // Stores the minimum index // having value is at least N int index = -1; // Iterator while i<=j while (i <= j) { // Stores the mid index // of the range [i, j] int mid = i + (j - i) / 2; // If P[mid] is at least N if (P[mid] >= N) { // Update the value of // mid to index index = mid; // Update the value of j j = mid - 1; } // Update the value of i else { i = mid + 1; } } // Return the resultant index return index; } // Function to find the minimum number // of days required to work to at least // arr[i] points for every array element void minDays(vector< int > P, vector< int > arr) { // Traverse the array P[] for ( int i = 1; i < P.size(); i++) { // Find the prefix sum P[i] += P[i] + P[i - 1]; } // Traverse the array arr[] for ( int i = 0; i < arr.size(); i++) { // Find the minimum index of // the array having value // at least arr[i] int index = binarySeach(P, arr[i]); // If the index is not -1 if (index != -1) { cout << index + 1 << " " ; } // Otherwise else { cout << -1 << " " ; } } } // Driver Code int main() { vector< int > arr = { 400, 200, 700, 900, 1400 }; vector< int > P = { 100, 300, 400, 500, 600 }; minDays(P, arr); return 0; } // This code is contributed by nirajgusain5 |
Java
// Java program for the above approach public class GFG { // Function to find the minimum number // of days required to work to at least // arr[i] points for every array element static void minDays( int [] P, int [] arr) { // Traverse the array P[] for ( int i = 1 ; i < P.length; i++) { // Find the prefix sum P[i] += P[i] + P[i - 1 ]; } // Traverse the array arr[] for ( int i = 0 ; i < arr.length; i++) { // Find the minimum index of // the array having value // at least arr[i] int index = binarySeach( P, arr[i]); // If the index is not -1 if (index != - 1 ) { System.out.print( index + 1 + " " ); } // Otherwise else { System.out.print( - 1 + " " ); } } } // Function to find the lower bound // of N using binary search static int binarySeach( int [] P, int N) { // Stores the lower bound int i = 0 ; // Stores the upper bound int j = P.length - 1 ; // Stores the minimum index // having value is at least N int index = - 1 ; // Iterator while i<=j while (i <= j) { // Stores the mid index // of the range [i, j] int mid = i + (j - i) / 2 ; // If P[mid] is at least N if (P[mid] >= N) { // Update the value of // mid to index index = mid; // Update the value of j j = mid - 1 ; } // Update the value of i else { i = mid + 1 ; } } // Return the resultant index return index; } // Driver Code public static void main(String[] args) { int [] arr = { 400 , 200 , 700 , 900 , 1400 }; int [] P = { 100 , 300 , 400 , 500 , 600 }; minDays(P, arr); } } |
Python3
# Python3 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 def minDays(P, arr): # Traverse the array P[] for i in range ( 1 , len (P)): # Find the prefix sum P[i] + = P[i] + P[i - 1 ] # Traverse the array arr[] for i in range ( len (arr)): # Find the minimum index of # the array having value # at least arr[i] index = binarySeach(P, arr[i]) # If the index is not -1 if (index ! = - 1 ): print (index + 1 , end = " " ) # Otherwise else : print ( - 1 , end = " " ) # Function to find the lower bound # of N using binary search def binarySeach(P, N): # Stores the lower bound i = 0 # Stores the upper bound j = len (P) - 1 # Stores the minimum index # having value is at least N index = - 1 # Iterator while i<=j while (i < = j): # Stores the mid index # of the range [i, j] mid = i + (j - i) / / 2 # If P[mid] is at least N if (P[mid] > = N): # Update the value of # mid to index index = mid # Update the value of j j = mid - 1 # Update the value of i else : i = mid + 1 # Return the resultant index return index # Driver Code if __name__ = = '__main__' : arr = [ 400 , 200 , 700 , 900 , 1400 ] P = [ 100 , 300 , 400 , 500 , 600 ] minDays(P, arr) # This code is contributed by mohit kumar 29. |
C#
// C# program for the above approach using System; class GFG{ // Function to find the minimum number // of days required to work to at least // arr[i] points for every array element static void minDays( int [] P, int [] arr) { // Traverse the array P[] for ( int i = 1; i < P.Length; i++) { // Find the prefix sum P[i] += P[i] + P[i - 1]; } // Traverse the array arr[] for ( int i = 0; i < arr.Length; i++) { // Find the minimum index of // the array having value // at least arr[i] int index = binarySeach(P, arr[i]); // If the index is not -1 if (index != -1) { Console.Write(index + 1 + " " ); } // Otherwise else { Console.Write(-1 + " " ); } } } // Function to find the lower bound // of N using binary search static int binarySeach( int [] P, int N) { // Stores the lower bound int i = 0; // Stores the upper bound int j = P.Length - 1; // Stores the minimum index // having value is at least N int index = -1; // Iterator while i<=j while (i <= j) { // Stores the mid index // of the range [i, j] int mid = i + (j - i) / 2; // If P[mid] is at least N if (P[mid] >= N) { // Update the value of // mid to index index = mid; // Update the value of j j = mid - 1; } // Update the value of i else { i = mid + 1; } } // Return the resultant index return index; } // Driver Code public static void Main( string [] args) { int [] arr = { 400, 200, 700, 900, 1400 }; int [] P = { 100, 300, 400, 500, 600 }; minDays(P, arr); } } // This code is contributed by ukasp |
Javascript
<script> // JavaScript program for the above approach // Function to find the lower bound // of N using binary search function binarySeach(P, N) { // Stores the lower bound var i = 0; // Stores the upper bound var j = P.length - 1; // Stores the minimum index // having value is at least N var index = -1; // Iterator while i<=j while (i <= j) { // Stores the mid index // of the range [i, j] var mid = i + parseInt((j - i) / 2); // If P[mid] is at least N if (P[mid] >= N) { // Update the value of // mid to index index = mid; // Update the value of j j = mid - 1; } // Update the value of i else { i = mid + 1; } } // Return the resultant index return index; } // Function to find the minimum number // of days required to work to at least // arr[i] points for every array element function minDays(P, arr) { // Traverse the array P[] for ( var i = 1; i < P.length; i++) { // Find the prefix sum P[i] += P[i] + P[i - 1]; } // Traverse the array arr[] for ( var i = 0; i < arr.length; i++) { // Find the minimum index of // the array having value // at least arr[i] var index = binarySeach(P, arr[i]); // If the index is not -1 if (index != -1) { document.write( (index + 1) + " " ); } // Otherwise else { document.write( -1 + " " ); } } } // Driver Code var arr = [400, 200, 700, 900, 1400]; var P = [100, 300, 400, 500, 600]; minDays(P, arr); </script> |
2 2 2 3 3
Time Complexity: O(N*log N)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!