Apply Operations to Make Sum of Array Greater Than or Equal to k

Apply Operations to Make Sum of Array Greater Than or Equal to k - Problem

You are given a positive integer k. Initially, you have an array nums = [1].

You can perform any of the following operations on the array any number of times (possibly zero):

Choose any element in the array and increase its value by 1.
Duplicate any element in the array and add it to the end of the array.

Return the minimum number of operations required to make the sum of elements of the final array greater than or equal to k.

Input & Output

Example 1 — Small Target

$ Input: k = 4

› Output: 2

💡 Note: Start with [1]. Duplicate to get [1,1] (1 op). Duplicate again to get [1,1,1,1] with sum=4 (total 2 ops).

Example 2 — Need Increments

$ Input: k = 11

› Output: 6

💡 Note: Start with [1]. After 3 duplicates: [1,1,1,1,1,1,1,1] sum=8. Then 3 increments to reach sum=11. Total: 3+3=6 operations.

Example 3 — Already Satisfied

$ Input: k = 1

› Output: 0

💡 Note: Initial array [1] already has sum=1 ≥ k=1, so no operations needed.

Constraints

1 ≤ k ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Initial State

Start with array [1], sum = 1

Two Operations

Increment any element (+1) or Duplicate entire array

Goal

Reach sum ≥ k with minimum operations

Key Takeaway

🎯 Key Insight: The optimal strategy balances duplicating for exponential growth with incrementing for precise adjustment

Asked in

G Google 15 f Meta 12 a Amazon 8

The key insight is to find the optimal balance between duplicating (doubling array size) and incrementing elements. The best approach uses mathematical enumeration to try different numbers of duplicate operations and find the minimum total cost. Time: O(log k), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Enumeration	O(2^k)	O(k)	Try all possible combinations of operations to find minimum
Optimal Mathematical Solution	O(log k)	O(1)	Use mathematical analysis to find the optimal balance of operations
Greedy Strategy	O(log k)	O(1)	Make locally optimal choices between incrementing and duplicating

Brute Force Enumeration — Algorithm Steps

Generate all possible operation sequences
For each sequence, calculate final sum
Return minimum operations among valid sequences

Visualization

Tap to expand

Step-by-Step Walkthrough

Initial State

Start with array [1], sum = 1

Branch Operations

Try both increment and duplicate at each step

Find Minimum

Return shortest path to sum >= k

Code -

solution.c — C

#include <stdio.h>
#include <limits.h>

int min(int a, int b) {
    return a < b ? a : b;
}

int dfs(int currentSum, int ops, int k) {
    if (currentSum >= k) {
        return ops;
    }
    
    int minOps = INT_MAX;
    
    int arrayLength = 1;
    for (int i = 0; i < ops; i++) {
        if (i % 2 == 1) {
            arrayLength *= 2;
        }
    }
    
    minOps = min(minOps, dfs(currentSum + arrayLength, ops + 1, k));
    minOps = min(minOps, dfs(currentSum * 2, ops + 1, k));
    
    return minOps;
}

int solution(int k) {
    return dfs(1, 0, k);
}

int main() {
    int k;
    scanf("%d", &k);
    
    int result = solution(k);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2^k)

Each operation has 2 choices, leading to exponential combinations

✓ Linear Growth

Space Complexity

O(k)

Recursion stack depth proportional to number of operations

✓ Linear Space

8.7K Views

Medium Frequency

~15 min Avg. Time

234 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 Enumeration — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler