1558-得到目标数组的最少函数调用次数

给你一个与 nums 大小相同且初始值全为 0 的数组 arr ，请你调用以上函数得到整数数组 nums 。

请你返回将 arr 变成 nums 的最少函数调用次数。

答案保证在 32 位有符号整数以内。

示例 1：

**输入：** nums = [1,5]
**输出：** 5
**解释：** 给第二个数加 1 ：[0, 0] 变成 [0, 1] （1 次操作）。
将所有数字乘以 2 ：[0, 1] -> [0, 2] -> [0, 4] （2 次操作）。
给两个数字都加 1 ：[0, 4] -> [1, 4] -> **[1, 5]** （2 次操作）。
总操作次数为：1 + 2 + 2 = 5 。

示例 2：

**输入：** nums = [2,2]
**输出：** 3
**解释：** 给两个数字都加 1 ：[0, 0] -> [0, 1] -> [1, 1] （2 次操作）。
将所有数字乘以 2 ： [1, 1] -> **[2, 2]** （1 次操作）。
总操作次数为： 2 + 1 = 3 。

示例 3：

**输入：** nums = [4,2,5]
**输出：** 6
**解释：** （初始）[0,0,0] -> [1,0,0] -> [1,0,1] -> [2,0,2] -> [2,1,2] -> [4,2,4] -> **[4,2,5]** （nums 数组）。

示例 4：

**输入：** nums = [3,2,2,4]
**输出：** 7

示例 5：

**输入：** nums = [2,4,8,16]
**输出：** 8

提示：

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

方法一：贪心

本题给定了两种操作：

让序列中某个数加 1；
让序列中所有数全体乘以 2。

询问你需要操作多少次，才能得到目标数组。

我们可以采用逆向思维，从目标数组转化为初始数组，支持两种操作：

让序列中某个数减 1；
让序列中所有数全体除以 2（要求序列中所有数均为偶数）。

询问你最少需要多少步才能让给定的数组中的全部元素变为 0。

我们贪心地考虑每一个数，显然我们应当尽可能多的执行第二种操作。因此我们只需要每次将序列中所有的奇数减 1，使其变为偶数，然后让整个偶数序列全体除以 2，直到所有数变为 0 为止。

对于任意一个数，我们从二进制的角度考虑：

如果它是奇数，那么它将被执行第一种操作。它的二进制表示中的末尾的 1 将会变成 0；
如果它是偶数，那么它将被执行第二种操作。它的二进制表示将会整体右移一位。

我们注意到对于任意一个数，它被执行第一种操作的次数等于它的二进制表示中的 1 的数量。我们只需要统计序列中所有数的二进制表示中 1 的数量之和，即可统计出第一种操作的数量。而第二种操作是全体数共同执行的，它的执行次数取决于序列中所有数的二进制表示的最高位数。我们只需要记录序列中最大值的二进制表示的位数，即可算出第二种操作的数量。

代码

[sol1-C++]class Solution {
public:
    int minOperations(vector<int>& nums) {
        int ret = 0, maxn = 0;
        for (auto num : nums) {
            maxn = max(maxn, num);
            while (num) {
                if (num & 1) {
                    ret++;
                }
                num >>= 1;
            }
        }
        if (maxn) {
            while (maxn) {
                ret++;
                maxn >>= 1;
            }
            ret--;
        }
        return ret;
    }
};

[sol1-C++]class Solution {
public:
    int minOperations(vector<int>& nums) {
        int ret = 0, maxn = 0;
        for (auto num : nums) {
            maxn = max(maxn, num);
            ret += __builtin_popcount(num);
        }
        if (maxn > 0) {
            ret += 31 - __builtin_clz(maxn);
        }
        return ret;
    }
};

[sol1-C]int minOperations(int* nums, int numsSize) {
    int ret = 0, maxn = 0;
    for (int i = 0; i < numsSize; i++) {
        maxn = fmax(maxn, nums[i]);
        while (nums[i]) {
            if (nums[i] & 1) {
                ret++;
            }
            nums[i] >>= 1;
        }
    }
    if (maxn) {
        while (maxn) {
            ret++;
            maxn >>= 1;
        }
        ret--;
    }
    return ret;
}

[sol1-Java]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;
    }
}

[sol1-Python3]class Solution:
    def minOperations(self, nums: List[int]) -> int:
        maxn = max(nums)
        ret = 0
        for num in nums:
            while num > 0:
                if num & 1:
                    ret += 1
                num >>= 1
        if maxn > 0:
            while maxn > 0:
                ret += 1
                maxn >>= 1
            ret -= 1
        
        return ret

复杂度分析

时间复杂度：O(n \times m)，其中 n 是数组 nums 的长度，m 是数组中元素的二进制表示的最大位数，本题中这些元素均为 32 位有符号整型数，因此 m<32。
空间复杂度：O(1)。