# 1558. 得到目标数组的最少函数调用次数
### 题目地址（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
```
### 前置知识
* 模拟
### 公司
* 暂无
### 思路
我们采用模拟的思路。 模拟指的是题目让我干什么，我干什么。
由于只能进行两种操作， 因此总的操作数就是两种操作的和。这里使用两个变量分别记录两种操作的数目，最后将其和返回即可。
由于题目给的参数是目标值， 其实我们这里也可以采用逆向思考， 即从 nums 递归到全零数组，这对结果不会产生影响。
```py
class Solution:
def minOperations(self, nums: List[int]) -> int:
max_multi = add = 0
for num in nums:
# your code here
return max_multi + add
```
算法：
* 从左到右遍历数组中的每一项
* 如果该项是奇数，则需要减去 1，同时 add 操作 + 1
* 如果该项是大于 0 的偶数， 则需要进行 除 2 操作，同时 multi 操作 + 1
* 每次遍历都会产生一个 multi，而由于 multi 次数取决于数组最大项，因此我们需要维护全局最大的 multi
* 最后的结果就是 add + 全局最大的 multi
### 关键点
* 逆向思考
* 使用两个变量分别记录 add 和 multi 的次数
* multi 取决于整个数组最大的数，add 取决于数组出现奇数的次数
### 代码
代码支持：Python3
```python
class Solution:
def minOperations(self, nums: List[int]) -> int:
max_multi = add = 0
for num in nums:
multi = 0
while num > 0:
if num & 1 == 1:
add += 1
num -= 1
if num >= 2:
multi += 1
num //= 2
max_multi = max(max_multi, multi)
return max_multi + add
```
**复杂度分析**
* 时间复杂度：$O(N \* (max\_multi + add))$，其中 N 为 nums 的长度。
* 空间复杂度：$O(1)$
更多题解可以访问我的 LeetCode 题解仓库： 。 目前已经 37K star 啦。
关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/1558.minimum-numbers-of-function-calls-to-make-target-array.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.