LeetCode 1558. Get the minimum number of function calls of the target array

1558. Get the minimum number of function calls to the target array

Give you a nums The size is the same and the initial value is 0 Array of arr , Please call the above function to get the integer array nums .

Please return and will arr become nums Minimum number of function calls .

The answer is guaranteed in 32 Bits within signed integers .

Example 1：

 Input ：nums = [1,5]
 Output ：5
 explain ： Add... To the second number  1 ：[0, 0]  become  [0, 1] （1  operations ）.
 Multiply all numbers by  2 ：[0, 1] -> [0, 2] -> [0, 4] （2  operations ）.
 Add... To both numbers  1 ：[0, 4] -> [1, 4] -> [1, 5] （2  operations ）.
 The total number of operations is ：1 + 2 + 2 = 5 .

Example 2：

 Input ：nums = [2,2]
 Output ：3
 explain ： Add... To both numbers  1 ：[0, 0] -> [0, 1] -> [1, 1] （2  operations ）.
 Multiply all numbers by  2 ： [1, 1] -> [2, 2] （1  operations ）.
 The total number of operations is ： 2 + 1 = 3 .

Example 3：

 Input ：nums = [4,2,5]
 Output ：6
 explain ：（ initial ）[0,0,0] -> [1,0,0] -> [1,0,1] -> [2,0,2] -> [2,1,2] -> [4,2,4] -> [4,2,5] （nums  Array ）.

Example 4：

 Input ：nums = [3,2,2,4]
 Output ：7

Example 5：

 Input ：nums = [2,4,8,16]
 Output ：8

Tips ：

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

Two 、 Method 1

greedy

class Solution {
    
    public int minOperations(int[] nums) {
    
        int ret = 0, maxn = 0;
        for (int num : nums) {
    
            maxn = Math.max(maxn, num);
            while (num != 0) {
    
                if ((num & 1) != 0) {
    
                    ret++;
                }
                num >>= 1;
            }
        }
        if (maxn != 0) {
    
            while (maxn != 0) {
    
                ret++;
                maxn >>= 1;
            }
            ret--;
        }
        return ret;
    }
}

Complexity analysis

• Time complexity ：O(n×m), among nn It's an array nums The length of ,m Is the maximum number of bits of the binary representation of the elements in the array , These elements in this question are 32 Bit signed integers , therefore m<32.

• Spatial complexity ：O(1).