Given N elements that have two costs associated with them that are represented in two arrays Costs1[] and Costs2[] of length N each and an integer budget. The task is to find the maximum number of consecutive elements that can be bought when the cost of buying k consecutive elements is calculated as max(costs1) + k*sum(costs2), where max(costs1) is the max of Costs1[] among the k elements and sum(costs2) is the sum of Costs2[] of the selected k elements.
Examples:
Input: Costs1[] = {3, 6, 1, 3, 4}, Costs2[] = {2, 1, 3, 4, 5}, budget = 25
Output: 3
Explanation: Consider the first 3 elements.
The total cost will be max(3, 6, 1) + 3 * sum(2, 1, 3) = 6 + 3 * 6 = 24 which is less than 25.
It can be shown that it is not possible to select more than 3 consecutive elements within budget.Input: Costs1[] = {12, 13, 19}, Costs2[] = {9, 7, 6}, budget = 18
Output: 0
Explanation: No element can be bought that does not exceed the budget, so we return 0.
Approach: To solve the problem follow the below idea:
Use sliding window technique to get the value for subarray [start, end]. If value exceeds budget move start and remove values associated with start to get new value and each time take maximum of the answer and length of the subarray.
Follow these steps to solve the problem:
- Take two pointers i and j for the start and end of the window, initialize both with 0, and a multiset for keeping the track of maximum among Costs1[].
- Include the jth elements and add Costs2[j] to runningCost and insert Costs1[j] to multiset.
- Calculate the total cost of the current window by adding the maximum among Costs1[] from the multiset and runningCost of the window.
- If the cost is greater than the budget then remove the ith element from the start of the window and update runningCost by subtracting Costs2[i].
- Also, remove the occurrence of the Costs1[i] from the multiset to maintain the current maximum in that window.
- Else if runningCost is less than or equal to the budget then it’s a valid window. So update the answer with the maximum of answer and length of the current window (j – i + 1).
- Return the answer when the loop ends.
Below is the implementation of the above approach.
C++
// C++ code to implement the approach #include <bits/stdc++.h> using namespace std; // Function to find the maximum number // of consecutive elements that can be bought int maximumObjects(vector< int >& Costs1, vector< int >& Costs2, int budget) { int n = Costs1.size(); // totalCost = total cost of k objects // runningCost to keep sum of Costs2 int totalCost = 0, runningCost = 0; int i = 0, j = 0, ans = 0; // Stores elements in ascending // order with repeated value allowed, // as there can be two values equal // to maximum value, even after // removing one maximum value from // window we may have another element // with same value as previous // max value multiset< int > ms; while (j < n) { ms.insert(Costs1[j]); runningCost += Costs2[j]; totalCost = *ms.rbegin() + (j - i + 1) * runningCost; // If totalCost > budget // slide the window if (totalCost > budget) { runningCost -= Costs2[i]; // Delete Costs1[i] from // multiset to keep max updated ms.erase(ms.find(Costs1[i])); i++; } // Keep storing the max possible // number of consecutive objects for // totalCost <= budget else ans = max(ans, j - i + 1); j++; } return ans; } // Driver code int main() { vector< int > Costs1 = { 3, 6, 1, 3, 4 }; vector< int > Costs2 = { 2, 1, 3, 4, 5 }; int budget = 25; // Function Call cout << maximumObjects(Costs1, Costs2, budget); return 0; } |
Java
// Java code to implement the approach import java.io.*; import java.util.*; class GFG { // Function to find the maximum number // of consecutive elements that can be bought public static int maximumObjects(List<Integer> Costs1, List<Integer> Costs2, int budget) { int n = Costs1.size(); // totalCost = total cost of k objects // runningCost to keep sum of Costs2 int totalCost = 0 , runningCost = 0 ; int i = 0 , j = 0 , ans = 0 ; // Stores elements in ascending // order with repeated value allowed, // as there can be two values equal // to maximum value, even after // removing one maximum value from // window we may have another element // with same value as previous // max value TreeSet<Integer> ms = new TreeSet<>(); while (j < n) { ms.add(Costs1.get(j)); runningCost += Costs2.get(j); totalCost = ms.last() + (j - i + 1 ) * runningCost; // If totalCost > budget // slide the window if (totalCost > budget) { runningCost -= Costs2.get(i); // Delete Costs1[i] from // multiset to keep max updated ms.remove(Costs1.get(i)); i++; } // Keep storing the max possible // number of consecutive objects for // totalCost <= budget else ans = Math.max(ans, j - i + 1 ); j++; } return ans; } public static void main(String[] args) { List<Integer> Costs1 = new ArrayList<>(); Costs1.add( 3 ); Costs1.add( 6 ); Costs1.add( 1 ); Costs1.add( 3 ); Costs1.add( 4 ); List<Integer> Costs2 = new ArrayList<>(); Costs2.add( 2 ); Costs2.add( 1 ); Costs2.add( 3 ); Costs2.add( 4 ); Costs2.add( 5 ); int budget = 25 ; // Function Call System.out.println( maximumObjects(Costs1, Costs2, budget)); } } // This code is contributed by lokesh. |
Python3
# Python code to implement the approach # Function to find the maximum number # of consecutive elements that can be bought def maximumObjects(Costs1, Costs2, budget): n = len (Costs1) # totalCost = total cost of k objects # runningCost to keep sum of Costs2 totalCost = 0 runningCost = 0 i, j, ans = 0 , 0 , 0 # Stores elements in ascending # order with repeated value allowed, # as there can be two values equal # to maximum value, even after # removing one maximum value from # window we may have another element # with same value as previous # max value ms = set () while (j < n): ms.add(Costs1[j]) runningCost = runningCost + Costs2[j] totalCost = next ( iter (ms)) + (j - i + 1 ) * runningCost # If totalCost > budget # slide the window if (totalCost > budget): runningCost = runningCost - Costs2[i] # Delete Costs1[i] from # multiset to keep max updated ms.remove(Costs1[i]) i = i + 1 # Keep storing the max possible # number of consecutive objects for # totalCost <= budget else : ans = max (ans, j - i + 1 ) j = j + 1 return ans # Driver code Costs1 = [ 3 , 6 , 1 , 3 , 4 ] Costs2 = [ 2 , 1 , 3 , 4 , 5 ] budget = 25 # Function Call print (maximumObjects(Costs1, Costs2, budget)) # This code is contributed by Pushpesh Raj. |
C#
// C# code to implement the approach using System; using System.Collections.Generic; public class GFG { // Function to find the maximum number // of consecutive elements that can be bought public static int maximumObjects(List< int > Costs1, List< int > Costs2, int budget) { int n = Costs1.Count; // totalCost = total cost of k objects // runningCost to keep sum of Costs2 int totalCost = 0, runningCost = 0; int i = 0, j = 0, ans = 0; // Stores elements in ascending // order with repeated value allowed, // as there can be two values equal // to maximum value, even after // removing one maximum value from // window we may have another element // with same value as previous // max value SortedSet< int > ms = new SortedSet< int >(); while (j < n) { ms.Add(Costs1[j]); runningCost += Costs2[j]; totalCost = ms.Max + (j - i + 1) * runningCost; // If totalCost > budget // slide the window if (totalCost > budget) { runningCost -= Costs2[i]; // Delete Costs1[i] from // multiset to keep max updated ms.Remove(Costs1[i]); i++; } // Keep storing the max possible // number of consecutive objects for // totalCost <= budget else ans = Math.Max(ans, j - i + 1); j++; } return ans; } static public void Main() { // Code List< int > Costs1 = new List< int >(); Costs1.Add(3); Costs1.Add(6); Costs1.Add(1); Costs1.Add(3); Costs1.Add(4); List< int > Costs2 = new List< int >(); Costs2.Add(2); Costs2.Add(1); Costs2.Add(3); Costs2.Add(4); Costs2.Add(5); int budget = 25; // Function Call Console.WriteLine( maximumObjects(Costs1, Costs2, budget)); } } // This code is contributed by lokeshmvs21. |
Javascript
// JavaScript code to implement the approach // Function to find the maximum number // of consecutive elements that can be bought const maximumObjects = (Costs1, Costs2, budget) => { let n = Costs1.length; // totalCost = total cost of k objects // runningCost to keep sum of Costs2 let totalCost = 0, runningCost = 0; let i = 0, j = 0, ans = 0; // Stores elements in ascending // order with repeated value allowed, // as there can be two values equal // to maximum value, even after // removing one maximum value from // window we may have another element // with same value as previous // max value let ms = new Set(); while (j < n) { ms.add(Costs1[j]); runningCost += Costs2[j]; totalCost = ms.values().next().value + (j - i + 1) * runningCost; // If totalCost > budget // slide the window if (totalCost > budget) { runningCost -= Costs2[i]; // Delete Costs1[i] from // multiset to keep max updated if (ms.has(Costs1[i])) ms. delete (Costs1[i]); i++; } // Keep storing the max possible // number of consecutive objects for // totalCost <= budget else ans = Math.max(ans, j - i + 1); j++; } return ans; } // Driver code let Costs1 = [3, 6, 1, 3, 4]; let Costs2 = [2, 1, 3, 4, 5]; let budget = 25; // Function Call console.log(maximumObjects(Costs1, Costs2, budget)); // This code is contributed by rakeshsahni |
PHP
<?php // Function to find the maximum number // of consecutive elements that can be bought function maximumObjects( $Costs1 , $Costs2 , $budget ) { $n = count ( $Costs1 ); // totalCost = total cost of k objects // runningCost to keep sum of Costs2 $totalCost = 0; $runningCost = 0; $i = 0; $j = 0; $ans = 0; // Stores elements in ascending // order with repeated value allowed, // as there can be two values equal // to maximum value, even after // removing one maximum value from // window we may have another element // with same value as previous // max value $ms = array (); while ( $j < $n ) { array_push ( $ms , $Costs1 [ $j ]); $runningCost += $Costs2 [ $j ]; $totalCost = max( $ms ) + ( $j - $i + 1) * $runningCost ; // If totalCost > budget // slide the window if ( $totalCost > $budget ) { $runningCost -= $Costs2 [ $i ]; // Delete Costs1[i] from // multiset to keep max updated unset( $ms [ array_search ( $Costs1 [ $i ], $ms )]); $i ++; } // Keep storing the max possible // number of consecutive objects for // totalCost <= budget else $ans = max( $ans , $j - $i + 1); $j ++; } return $ans ; } // Driver code $Costs1 = array (3, 6, 1, 3, 4); $Costs2 = array (2, 1, 3, 4, 5); $budget = 25; // Function Call echo maximumObjects( $Costs1 , $Costs2 , $budget ); // This code is contributed by Kanishka Gupta ?> |
3
Time Complexity: O(N * log N)
Auxiliary Space: O(N)
Another Approach:
- Take two pointers i and j for the start and end of the window, initialize both with 0, and a deque for keeping the track of maximum among Costs1[].
- Include the jth element and add Costs2[j] to runningCost and insert Costs1[j] to the back of the deque.
- Remove all elements from the front of the deque until the current maximum among Costs1[] is at the front of the deque.
- Calculate the total cost of the current window by adding the maximum among Costs1[] from the front of the deque and runningCost of the window.
- If the cost is greater than the budget then remove the ith element from the start of the window and update runningCost by subtracting Costs2[i].
- Also, remove the front element from the deque if it is equal to Costs1[i] to maintain the current maximum in that window.
- Else if runningCost is less than or equal to the budget then it’s a valid window. So update the answer with the maximum of answer and length of the current window (j – i + 1).
- Return the answer when the loop ends.
C++
// C++ code to implement the approach #include <bits/stdc++.h> using namespace std; // Function to find the maximum number // of consecutive elements that can be bought int maximumObjects(vector< int >& Costs1, vector< int >& Costs2, int budget) { int n = Costs1.size(); // totalCost = total cost of k objects // runningCost to keep sum of Costs2 int totalCost = 0, runningCost = 0; int i = 0, j = 0, ans = 0; // Stores elements in descending order // to keep maximum in front deque< int > dq; while (j < n) { while (!dq.empty() && Costs1[j] >= dq.back()) dq.pop_back(); dq.push_back(Costs1[j]); runningCost += Costs2[j]; totalCost = dq.front() + (j - i + 1) * runningCost; // If totalCost > budget // slide the window if (totalCost > budget) { runningCost -= Costs2[i]; // Delete the current maximum if (dq.front() == Costs1[i]) dq.pop_front(); i++; } // Keep storing the max possible // number of consecutive objects for // totalCost <= budget else ans = max(ans, j - i + 1); j++; } return ans; } // Driver code int main() { vector< int > Costs1 = { 3, 6, 1, 3, 4 }; vector< int > Costs2 = { 2, 1, 3, 4, 5 }; int budget = 25; // Function Call cout << maximumObjects(Costs1, Costs2, budget); return 0; } |
Java
// java code to implement the approach import java.util.*; public class Main { // Function to find the maximum number // of consecutive elements that can be bought static int maximumObjects(List<Integer> Costs1, List<Integer> Costs2, int budget) { int n = Costs1.size(); // totalCost = total cost of k objects // runningCost to keep sum of Costs2 int totalCost = 0 , runningCost = 0 ; int i = 0 , j = 0 , ans = 0 ; // Stores elements in descending order // to keep maximum in front Deque<Integer> dq = new LinkedList<>(); while (j < n) { while (!dq.isEmpty() && Costs1.get(j) >= dq.peekLast()) dq.removeLast(); dq.addLast(Costs1.get(j)); runningCost += Costs2.get(j); totalCost = dq.peekFirst() + (j - i + 1 ) * runningCost; // If totalCost > budget // slide the window if (totalCost > budget) { runningCost -= Costs2.get(i); // Delete the current maximum if (dq.peekFirst() == Costs1.get(i)) dq.removeFirst(); i++; } // Keep storing the max possible // number of consecutive objects for // totalCost <= budget else ans = Math.max(ans, j - i + 1 ); j++; } return ans; } // Driver code public static void main(String[] args) { List<Integer> Costs1 = Arrays.asList( 3 , 6 , 1 , 3 , 4 ); List<Integer> Costs2 = Arrays.asList( 2 , 1 , 3 , 4 , 5 ); int budget = 25 ; // Function Call System.out.println( maximumObjects(Costs1, Costs2, budget)); } } |
Python3
from collections import deque def maximum_objects(Costs1, Costs2, budget): n = len (Costs1) # totalCost = total cost of k objects # runningCost to keep sum of Costs2 total_cost = 0 running_cost = 0 i = 0 j = 0 ans = 0 # Stores elements in descending order # to keep maximum in front dq = deque() while j < n: while dq and Costs1[j] > = dq[ - 1 ]: dq.pop() dq.append(Costs1[j]) running_cost + = Costs2[j] total_cost = dq[ 0 ] + (j - i + 1 ) * running_cost # If total_cost > budget # slide the window if total_cost > budget: running_cost - = Costs2[i] # Delete the current maximum if dq[ 0 ] = = Costs1[i]: dq.popleft() i + = 1 # Keep storing the max possible # number of consecutive objects for # total_cost <= budget else : ans = max (ans, j - i + 1 ) j + = 1 return ans # Driver code if __name__ = = '__main__' : Costs1 = [ 3 , 6 , 1 , 3 , 4 ] Costs2 = [ 2 , 1 , 3 , 4 , 5 ] budget = 25 # Function Call print (maximum_objects(Costs1, Costs2, budget)) |
C#
using System; using System.Collections.Generic; using System.Linq; class Program { // Function to find the maximum number // of consecutive elements that can be bought static int MaximumObjects(List< int > Costs1, List< int > Costs2, int budget) { int n = Costs1.Count; // totalCost = total cost of k objects // runningCost to keep sum of Costs2 int totalCost = 0, runningCost = 0; int i = 0, j = 0, ans = 0; // Stores elements in descending order // to keep maximum in front Queue< int > dq = new Queue< int >(); while (j < n) { while (dq.Any() && Costs1[j] >= dq.Last()) dq.Dequeue(); dq.Enqueue(Costs1[j]); runningCost += Costs2[j]; totalCost = dq.Peek() + (j - i + 1) * runningCost; // If totalCost > budget // slide the window if (totalCost > budget) { runningCost -= Costs2[i]; // Delete the current maximum if (dq.Peek() == Costs1[i]) dq.Dequeue(); i++; } // Keep storing the max possible // number of consecutive objects for // totalCost <= budget else ans = Math.Max(ans, j - i + 1); j++; } return ans; } // Driver code static void Main( string [] args) { List< int > Costs1 = new List< int >{ 3, 6, 1, 3, 4 }; List< int > Costs2 = new List< int >{ 2, 1, 3, 4, 5 }; int budget = 25; // Function Call Console.WriteLine( MaximumObjects(Costs1, Costs2, budget)); } } |
Javascript
function maximumObjects(Costs1, Costs2, budget) { let n = Costs1.length; // totalCost = total cost of k objects // runningCost to keep sum of Costs2 let totalCost = 0, runningCost = 0; let i = 0, j = 0, ans = 0; // Stores elements in descending order // to keep maximum in front let dq = []; while (j < n) { while (dq.length !== 0 && Costs1[j] >= dq[dq.length - 1]) dq.pop(); dq.push(Costs1[j]); runningCost += Costs2[j]; totalCost = dq[0] + (j - i + 1) * runningCost; // If totalCost > budget // slide the window if (totalCost > budget) { runningCost -= Costs2[i]; // Delete the current maximum if (dq[0] === Costs1[i]) dq.shift(); i++; } // Keep storing the max possible // number of consecutive objects for // totalCost <= budget else ans = Math.max(ans, j - i + 1); j++; } return ans; } // Driver code let Costs1 = [3, 6, 1, 3, 4]; let Costs2 = [2, 1, 3, 4, 5]; let budget = 25; // Function Call console.log(maximumObjects(Costs1, Costs2, budget)); |
3
Time Complexity: O(N*logN), Where N is the size of the array
Auxiliary Space: O(N)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!