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 _theminimum number of operations required to make the sum of elements of the final array greater than or equal to _k.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

Input: k = 11
Output: 5
Explanation:
We can do the following operations on the array `nums = [1]`:

  * Increase the element by `1` three times. The resulting array is `nums = [4]`.
  * Duplicate the element two times. The resulting array is `nums = [4,4,4]`.

The sum of the final array is `4 + 4 + 4 = 12` which is greater than or equal
to `k = 11`.  
The total number of operations performed is `3 + 2 = 5`.

Example 2

1
2
3
4

Input: k = 1
Output: 0
Explanation:
The sum of the original array is already greater than or equal to `1`, so no operations are needed.

Constraints

  • 1 <= k <= 10^5

Solution

Method 1 – Greedy Doubling and Increment

Intuition

The fastest way to reach or exceed k is to repeatedly double the sum (by duplicating the largest element) until we’re close to k, then increment as needed. Duplicating increases the sum exponentially, while incrementing is linear. We minimize operations by duplicating as much as possible, then incrementing the largest element to reach or exceed k.

Approach

  1. Start with nums = [1] and sum = 1.
  2. While sum < k:
  • If sum * 2 <= k, duplicate the largest element (double the sum).
  • Else, increment the largest element to reach or exceed k.
  1. Count the number of operations (duplications + increments).
  2. Edge case: If k == 1, no operations are needed.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
public:
   int minOperations(int k) {
      if (k == 1) return 0;
      int ans = 0, curr = 1;
      while (curr < k) {
        if (curr * 2 <= k) {
           curr *= 2;
           ans++;
        } else {
           ans += (k - curr);
           curr = k;
        }
      }
      return ans;
   }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
   public int minOperations(int k) {
      if (k == 1) return 0;
      int ans = 0, curr = 1;
      while (curr < k) {
        if (curr * 2 <= k) {
           curr *= 2;
           ans++;
        } else {
           ans += (k - curr);
           curr = k;
        }
      }
      return ans;
   }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution:
   def minOperations(self, k: int) -> int:
      if k == 1:
        return 0
      ans: int = 0
      curr: int = 1
      while curr < k:
        if curr * 2 <= k:
           curr *= 2
           ans += 1
        else:
           ans += (k - curr)
           curr = k
      return ans

Complexity

  • ⏰ Time complexity: O(log k) (since we double until close to k)
  • 🧺 Space complexity: O(1)