Salesforce VO 面试真题解析：Two Operations 最少操作次数

Two integer operations are defined as:

• ADD_1: Increment the integer by 1
• MULTIPLY_2: Multiply the integer by 2

Given an integer value k, determine the minimum number of operations it takes to get from 0 to k using the two operations specified above.

Example

kValues[i] = 8

Starting from 0, add 1, then multiply by 2 three times. It takes a minimum of 4 operations to get to 8, so store 4 in index 0 of the return array.

Function Description

Complete the function getMinOperations in the editor.

getMinOperations has the following parameter(s):

• kValues[n]: the given k values

Returns:

• int[n]: answers to a list of queries in the given order

Sample Input

n = 2
kValues = [5, 3]

Sample Output

4
3

Explanation

0. To get from 0 to kValues[0] = 5, ADD_1 -> MULTIPLY_2 -> MULTIPLY_2 -> ADD_1 to get 0 -> 1 -> 2 -> 4 -> 5. Because it took four operations, store 4 in index 0 of the return array.

1. To get from 0 to kValues[1] = 3, ADD_1 -> MULTIPLY_2 -> ADD_1 to get 0 -> 1 -> 2 -> 3. Because it took three operations, store 3 in index 1 of the return array.

Return the array [4, 3] as the answer.

这道 Salesforce VO 题本质上是“从 0 到 k 的最少步数”问题，只允许两种操作：加 1 和乘 2。关键思路是反向分析目标值：如果当前数是偶数，优先除以 2；如果是奇数，就先减 1 变成偶数。这样可以快速得到最少操作数，并且对每个查询独立计算即可。示例中 5 需要 4 步，3 需要 3 步，最终返回 [4, 3]。