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 searchint 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 elementvoid 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 Codeint 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 approachpublic 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 elementdef 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 searchdef 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 Codeif __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 approachusing System;class GFG{ // Function to find the minimum number// of days required to work to at least// arr[i] points for every array elementstatic 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 searchstatic 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 Codepublic 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 searchfunction 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 elementfunction 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 Codevar arr = [400, 200, 700, 900, 1400];var P = [100, 300, 400, 500, 600];minDays(P, arr);</script> |
Output:
2 2 2 3 3
Time Complexity: O(N*log N)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
