Problem

You are given an integer array nums. You have an integer array arr of the same length with all values set to 0 initially. You also have the following modify function:

You want to use the modify function to convert arr to nums using the minimum number of calls.

Return the minimum number of function calls to makenums fromarr.

The test cases are generated so that the answer fits in a 32-bit signed integer.

Examples

Example 1

1
2
3
4
5
6

Input: nums = [1,5]
Output: 5
Explanation: Increment by 1 (second element): [0, 0] to get [0, 1] (1 operation).
Double all the elements: [0, 1] -> [0, 2] -> [0, 4] (2 operations).
Increment by 1 (both elements)  [0, 4] -> [1, 4] -> **[1, 5]** (2 operations).
Total of operations: 1 + 2 + 2 = 5.

Example 2

1
2
3
4
5

Input: nums = [2,2]
Output: 3
Explanation: Increment by 1 (both elements) [0, 0] -> [0, 1] -> [1, 1] (2 operations).
Double all the elements: [1, 1] -> **[2, 2]** (1 operation).
Total of operations: 2 + 1 = 3.

Example 3

1
2
3

Input: nums = [4,2,5]
Output: 6
Explanation: (initial)[0,0,0] -> [1,0,0] -> [1,0,1] -> [2,0,2] -> [2,1,2] -> [4,2,4] -> **[4,2,5]**(nums).

Constraints

  • 1 <= nums.length <= 10^5
  • 0 <= nums[i] <= 10^9

Solution

Method 1 – Bit Manipulation & Greedy

Intuition

To reach nums from zeros, we need to increment each bit individually and double all elements together. The minimum number of operations is the sum of all set bits (increments) plus the maximum number of doublings needed for any element.

Approach

  1. For each number, count the number of set bits (increments needed).
  2. Track the maximum bit length (number of doublings needed).
  3. The answer is total increments plus max doublings.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
public:
    int minOperations(vector<int>& nums) {
        int inc = 0, dbl = 0;
        for (int v : nums) {
            inc += __builtin_popcount(v);
            dbl = max(dbl, v ? 32 - __builtin_clz(v) : 0);
        }
        return inc + (dbl ? dbl - 1 : 0);
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

func minOperations(nums []int) int {
    inc, dbl := 0, 0
    for _, v := range nums {
        for x := v; x > 0; x &= x - 1 {
            inc++
        }
        l := 0
        for x := v; x > 0; x >>= 1 {
            l++
        }
        if l > dbl {
            dbl = l
        }
    }
    if dbl > 0 {
        dbl--
    }
    return inc + dbl
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    public int minOperations(int[] nums) {
        int inc = 0, dbl = 0;
        for (int v : nums) {
            inc += Integer.bitCount(v);
            int l = v == 0 ? 0 : 32 - Integer.numberOfLeadingZeros(v);
            dbl = Math.max(dbl, l);
        }
        return inc + (dbl > 0 ? dbl - 1 : 0);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    fun minOperations(nums: IntArray): Int {
        var inc = 0
        var dbl = 0
        for (v in nums) {
            inc += v.countOneBits()
            val l = if (v == 0) 0 else 32 - v.countLeadingZeroBits()
            dbl = maxOf(dbl, l)
        }
        return inc + if (dbl > 0) dbl - 1 else 0
    }
}
1
2
3
4
5
6
7
8
9

class Solution:
    def minOperations(self, nums: list[int]) -> int:
        inc: int = 0
        dbl: int = 0
        for v in nums:
            inc += bin(v).count('1')
            l = v.bit_length()
            dbl = max(dbl, l)
        return inc + (dbl - 1 if dbl > 0 else 0)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

impl Solution {
    pub fn min_operations(nums: Vec<i32>) -> i32 {
        let mut inc = 0;
        let mut dbl = 0;
        for v in nums {
            inc += v.count_ones() as i32;
            let l = if v == 0 { 0 } else { 32 - v.leading_zeros() };
            dbl = dbl.max(l as i32);
        }
        inc + if dbl > 0 { dbl - 1 } else { 0 }
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    minOperations(nums: number[]): number {
        let inc = 0, dbl = 0;
        for (const v of nums) {
            inc += v.toString(2).split('1').length - 1;
            const l = v === 0 ? 0 : v.toString(2).length;
            dbl = Math.max(dbl, l);
        }
        return inc + (dbl > 0 ? dbl - 1 : 0);
    }
}

Complexity

  • ⏰ Time complexity: O(n log m) — For each number, we count bits and bit length, m is max value.
  • 🧺 Space complexity: O(1) — Only a few variables are used.