Data Modelling & AI Data Structure & Algorithm

Minimum days to make Array elements with value at least K sum at least X

24 June 2025

4

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.

Output:

Time Complexity: O(N*log X)
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!

1 COMMENT

Peyote Cactus Till Salu I Sverige 20 November 2025 At 4:50 pm

… [Trackback]

[…] Info to that Topic: geeksforgeeks.org/minimum-days-to-make-array-elements-with-value-at-least-k-sum-at-least-x/ […]

Log in to leave a comment

Minimum days to make Array elements with value at least K sum at least X

C++

Java

C#

Javascript

Python3

Adding Persistent Memory to Claude Code with the Lightweight memsearch Plugin

GLM-5 vs. MiniMax M2.5 vs. Gemini 3 Deep Think: Which Model Fits Your AI Agent Stack?

We Extracted OpenClaw’s Memory System and Open-Sourced It (memsearch)

1 COMMENT

LEAVE A REPLY Cancel reply

Most Popular

Android 17 is fixing battery drain, camera crashes, and display glitches you’ve probably hit

Google Photos could be working on new ways to transform your videos

The two most extreme phones ever. [Video]

What to watch this weekend: You can Outlast: The Jungle or try Surviving Earth

EDITOR PICKS

Android 17 is fixing battery drain, camera crashes, and display glitches you’ve probably hit

Google Photos could be working on new ways to transform your videos

The two most extreme phones ever. [Video]

POPULAR POSTS

Android 17 is fixing battery drain, camera crashes, and display glitches you’ve probably hit

Google Photos could be working on new ways to transform your videos

The two most extreme phones ever. [Video]

POPULAR CATEGORY

ABOUT US

FOLLOW US