Given two integers X, K, and two arrays arr[] and R[] both consisting of N positive integers where R[i] denotes the amount by which arr[i] increases in one day, the task is to find the minimum number of days after which the sum of array elements having value greater than or equal to K becomes at least X.
Examples:
Input: X = 100, K = 45, arr[] = {2, 5, 2, 6}, R[] = {10, 13, 15, 12}
Output: 4
Explanation:
Consider the following values of array after each day:
- Day 1: After the day 1, all array element modifies to {12, 18, 17, 18}. The sum of elements having values >= K(= 45) is 0.
- Day 2: After the day 2, all array element modifies to {22, 31, 32, 30}. The sum of elements having values >= K(= 45) is 0.
- Day 3: After the day 3, all array element modifies to {32, 44, 47, 42}. The sum of elements having values >= K(= 45) is 47.
- Day 4: After the day 4, all array element modifies to {42, 57, 62, 54}. The sum of elements having values >= K(= 45) is 57 + 62 + 54 = 167, which is at least X(= 100).
Therefore, the minimum number of days required is 4.
Input: X = 65, K = 10, arr[] = {1, 1, 1, 1, 3}, R[] = {2, 1, 2, 2, 1}
Output: 9
Naive Approach: The simplest approach to solve the given problem is to keep incrementing the number of days and whenever the sum of the array elements having a value at least K becomes greater than or equal to X. After incrementing for D days, print the value of the current number of days obtained.
Time Complexity: O(N*X)
Auxiliary Space: O(1)
Efficient Approach: The above approach can also be optimized by using Binary Search. Follow the steps below to solve the problem:
- Initialize two variables, say low as 0 and high as X.
- Initialize a variable, say minDays that stores the minimum number of days.
- Iterate until the value of low is at most high and perform the following steps:
- Initialize a variable mid as low + (high – low)/2 and variable, say sum as 0 to store the sum of array elements after mid number of days.
- Traverse the array, arr[] using the variable i and perform the following steps:
- Initialize a variable temp as (arr[i] + R[i]*mid).
- If the value of temp is not less than K add the value of temp to sum.
- If the value of sum is at least X, then update the value of minDays to mid and the value of high to (mid – 1).
- Otherwise, update the value of low to (mid + 1).
- After completing the above steps, print the value of minDays as the resultant minimum number of days.
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 minimum number // of days such that the sum of array // elements >= K is at least X void findMinDays( int arr[], int R[], int N, int X, int K) { // Initialize the boundaries of // search space int low = 0, high = X; int minDays; // Perform the binary search while (low <= high) { // Find the value of mid int mid = (low + high) / 2; int sum = 0; // Traverse the array, arr[] for ( int i = 0; i < N; i++) { // Find the value of arr[i] // after mid number of days int temp = arr[i] + R[i] * mid; // Check if temp is not // less than K if (temp >= K) { // Update the value // of sum sum += temp; } } // Check if the value of sum // is greater than X if (sum >= X) { // Update value of high minDays = mid; high = mid - 1; } // Update the value of low else { low = mid + 1; } } // Print the minimum number // of days cout << minDays; } // Driver Code int main() { int X = 100, K = 45; int arr[] = { 2, 5, 2, 6 }; int R[] = { 10, 13, 15, 12 }; int N = sizeof (arr) / sizeof (arr[0]); findMinDays(arr, R, N, X, K); return 0; } |
Java
// Java program for the above approach import java.io.*; class GFG{ // Function to find the minimum number // of days such that the sum of array // elements >= K is at least X static void findMinDays( int arr[], int R[], int N, int X, int K) { // Initialize the boundaries of // search space int low = 0 , high = X; int minDays = - 1 ; // Perform the binary search while (low <= high) { // Find the value of mid int mid = (low + high) / 2 ; int sum = 0 ; // Traverse the array, arr[] for ( int i = 0 ; i < N; i++) { // Find the value of arr[i] // after mid number of days int temp = arr[i] + R[i] * mid; // Check if temp is not // less than K if (temp >= K) { // Update the value // of sum sum += temp; } } // Check if the value of sum // is greater than X if (sum >= X) { // Update value of high minDays = mid; high = mid - 1 ; } // Update the value of low else { low = mid + 1 ; } } // Print the minimum number // of days System.out.println(minDays); } // Driver Code public static void main(String[] args) { int X = 100 , K = 45 ; int arr[] = { 2 , 5 , 2 , 6 }; int R[] = { 10 , 13 , 15 , 12 }; int N = arr.length; findMinDays(arr, R, N, X, K); } } // This code is contributed by Potta Lokesh |
C#
// C# program for the above approach using System; class GFG { // Function to find the minimum number // of days such that the sum of array // elements >= K is at least X static void findMinDays( int [] arr, int [] R, int N, int X, int K) { // Initialize the boundaries of // search space int low = 0, high = X; int minDays = -1; // Perform the binary search while (low <= high) { // Find the value of mid int mid = (low + high) / 2; int sum = 0; // Traverse the array, arr[] for ( int i = 0; i < N; i++) { // Find the value of arr[i] // after mid number of days int temp = arr[i] + R[i] * mid; // Check if temp is not // less than K if (temp >= K) { // Update the value // of sum sum += temp; } } // Check if the value of sum // is greater than X if (sum >= X) { // Update value of high minDays = mid; high = mid - 1; } // Update the value of low else { low = mid + 1; } } // Print the minimum number // of days Console.Write(minDays); } // Driver Code public static void Main( string [] args) { int X = 100, K = 45; int [] arr = { 2, 5, 2, 6 }; int [] R = { 10, 13, 15, 12 }; int N = arr.Length; findMinDays(arr, R, N, X, K); } } // This code is contributed by ukasp. |
Javascript
<script> // Javascript program for the above approach // Function to find the minimum number // of days such that the sum of array // elements >= K is at least X function findMinDays(arr, R, N, X, K) { // Initialize the boundaries of // search space let low = 0, high = X; let minDays; // Perform the binary search while (low <= high) { // Find the value of mid let mid = Math.floor((low + high) / 2); let sum = 0; // Traverse the array, arr[] for (let i = 0; i < N; i++) { // Find the value of arr[i] // after mid number of days let temp = arr[i] + R[i] * mid; // Check if temp is not // less than K if (temp >= K) { // Update the value // of sum sum += temp; } } // Check if the value of sum // is greater than X if (sum >= X) { // Update value of high minDays = mid; high = mid - 1; } // Update the value of low else { low = mid + 1; } } // Print the minimum number // of days document.write(minDays); } // Driver Code let X = 100, K = 45; let arr = [2, 5, 2, 6]; let R = [10, 13, 15, 12]; let N = arr.length findMinDays(arr, R, N, X, K); // This code is contributed by _saurabh_jaiswal. </script> |
Python3
# Python 3 program for the above approach # Function to find the minimum number # of days such that the sum of array # elements >= K is at least X def findMinDays(arr, R, N, X, K): # Initialize the boundaries of # search space low = 0 high = X minDays = 0 # Perform the binary search while (low < = high): # Find the value of mid mid = (low + high) / / 2 sum = 0 # Traverse the array, arr[] for i in range (N): # Find the value of arr[i] # after mid number of days temp = arr[i] + R[i] * mid # Check if temp is not # less than K if (temp > = K): # Update the value # of sum sum + = temp # Check if the value of sum # is greater than X if ( sum > = X): # Update value of high minDays = mid high = mid - 1 # Update the value of low else : low = mid + 1 # Print the minimum number # of days print (minDays) # Driver Code if __name__ = = '__main__' : X = 100 K = 45 arr = [ 2 , 5 , 2 , 6 ] R = [ 10 , 13 , 15 , 12 ] N = len (arr) findMinDays(arr, R, N, X, K) # This code is contributed by SURENDRA_GANGWAR. |
4
Time Complexity: O(N*log X)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!