Minimum Time to Make Array Sum At Most x - Practice Coding Problems

Minimum Time to Make Array Sum At Most x - Problem

You are given two 0-indexed integer arrays nums1 and nums2 of equal length. Every second, for all indices 0 <= i < nums1.length, the value of nums1[i] is incremented by nums2[i].

After this increment operation is done, you can perform the following operation:

Choose an index 0 <= i < nums1.length and make nums1[i] = 0.

You are also given an integer x.

Return the minimum time in which you can make the sum of all elements of nums1 to be less than or equal to x, or -1 if this is not possible.

Input & Output

Example 1 — Basic Case

$ Input: nums1 = [1,2,3], nums2 = [1,4,2], x = 4

› Output: 3

💡 Note: At time 3: We can operate on index 1 (highest growth rate) at time 1, index 2 at time 2, and index 0 at time 3. After simulation, the final sum becomes ≤ 4.

Example 2 — Already Satisfied

$ Input: nums1 = [1,1,1], nums2 = [1,1,1], x = 5

› Output: 0

💡 Note: Initial sum is 3 ≤ 5, so no operations needed.

Example 3 — Impossible Case

$ Input: nums1 = [1,2,3], nums2 = [3,3,3], x = 4

› Output: -1

💡 Note: Even with optimal operations, we cannot reduce the sum to ≤ 4 due to high growth rates.

Constraints

1 ≤ nums1.length == nums2.length ≤ 1000
1 ≤ nums1[i], nums2[i] ≤ 1000
1 ≤ x ≤ 10⁶

Visualization

Tap to expand

Understanding the Visualization

Initial State

nums1=[1,2,3], nums2=[1,4,2], x=4. Sum=6 > 4

Growth & Operations

Each second: increment by nums2, then optionally reset one element

Goal

Find minimum time to achieve sum ≤ 4

Key Takeaway

🎯 Key Insight: Sort by growth rates and use DP to find optimal operation schedule

Asked in

G Google 15 a Amazon 12 M Meta 8 M Microsoft 6

This problem requires finding the minimum time to reduce array sum through strategic operations. The key insight is to sort elements by growth rate and use dynamic programming with binary search. The optimal approach combines sorting by nums2[i] values with 2D DP to track minimum achievable sums. Time: O(n² × log n), Space: O(n²)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Simulation	O(n! × n²)	O(n)	Try all possible sequences of operations for each time step
Dynamic Programming with Sorting	O(n² × log(n × max(nums1)))	O(n²)	Sort by nums2 values and use DP to find optimal operation sequence

Brute Force Simulation — Algorithm Steps

For each time t from 0 to n
Generate all possible operation sequences of length t
Simulate each sequence and check final sum
Return minimum t that works

Visualization

Tap to expand

Step-by-Step Walkthrough

Input Arrays

nums1=[1,2,3], nums2=[1,4,2], x=4

Try Sequences

Test all permutations of operations for each time t

Find Minimum

Return smallest t where sum ≤ x

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

bool tryPermutations(int* nums1, int* nums2, int n, int x, int t, int* indices, int pos, bool* used) {
    if (pos == t) {
        long long current[n];
        for (int i = 0; i < n; i++) {
            current[i] = nums1[i];
        }
        
        for (int timeStep = 0; timeStep < t; timeStep++) {
            for (int i = 0; i < n; i++) {
                current[i] += nums2[i];
            }
            current[indices[timeStep]] = 0;
        }
        
        long long sum = 0;
        for (int i = 0; i < n; i++) {
            sum += current[i];
        }
        return sum <= x;
    }
    
    for (int i = 0; i < n; i++) {
        if (!used[i]) {
            used[i] = true;
            indices[pos] = i;
            if (tryPermutations(nums1, nums2, n, x, t, indices, pos + 1, used)) {
                return true;
            }
            used[i] = false;
        }
    }
    return false;
}

int solution(int* nums1, int* nums2, int n, int x) {
    long long sum = 0;
    for (int i = 0; i < n; i++) {
        sum += nums1[i];
    }
    if (sum <= x) return 0;
    
    for (int t = 1; t <= n; t++) {
        int indices[n];
        bool used[n];
        for (int i = 0; i < n; i++) used[i] = false;
        
        if (tryPermutations(nums1, nums2, n, x, t, indices, 0, used)) {
            return t;
        }
    }
    
    return -1;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse nums1
    int nums1[1000], n1 = 0;
    char* token = strtok(line, "[],\n");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] != ' ') {
            nums1[n1++] = atoi(token);
        }
        token = strtok(NULL, "[],\n");
    }
    
    fgets(line, sizeof(line), stdin);
    
    // Parse nums2
    int nums2[1000], n2 = 0;
    token = strtok(line, "[],\n");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] != ' ') {
            nums2[n2++] = atoi(token);
        }
        token = strtok(NULL, "[],\n");
    }
    
    int x;
    scanf("%d", &x);
    
    printf("%d\n", solution(nums1, nums2, n1, x));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n! × n²)

For each time t, we try all t! permutations of operations, each taking O(n) time to simulate

⚠ Quadratic Growth

Space Complexity

O(n)

Storage for current state and recursion stack

⚡ Linearithmic Space

23.1K Views

Medium Frequency

~35 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Simulation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler