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

Start with nums = [1] and sum = 1.
While sum < k:

If sum * 2 <= k, duplicate the largest element (double the sum).
Else, increment the largest element to reach or exceed k.

Count the number of operations (duplications + increments).
Edge case: If k == 1, no operations are needed.

Code

[{"language":"C++","code":"class Solution {\npublic:\n   int minOperations(int k) {\n      if (k == 1) return 0;\n      int ans = 0, curr = 1;\n      while (curr < k) {\n        if (curr * 2 <= k) {\n           curr *= 2;\n           ans++;\n        } else {\n           ans += (k - curr);\n           curr = k;\n        }\n      }\n      return ans;\n   }\n};","lang":"cpp","html":"<pre class=\"shiki shiki-themes github-light github-dark\" style=\"background-color:#fff;--shiki-dark-bg:#24292e;color:#24292e;--shiki-dark:#e1e4e8\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">class</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> Solution</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> {</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">public:</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">   int</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> minOperations</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">(</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">int</span><span style=\"color:#E36209;--shiki-dark:#FFAB70\"> k</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">) {</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">      if</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> (k </span><span style=\"color:#D73A49;--shiki-dark:#F97583\">==</span><span style=\"color:#005CC5;--shiki-dark:#79B8FF\"> 1</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">) </span><span style=\"color:

Related Tags