Your task is to form an integer array nums
from an initial array of zeros arr
that is the same size as nums
.
Return the minimum number of function calls to make nums
from arr
.
The answer is guaranteed to fit in a 32-bit signed integer.
Example 1:
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:
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:
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).
Example 4:
Input: nums = [3,2,2,4] Output: 7
Example 5:
Input: nums = [2,4,8,16] Output: 8
Constraints:
1 <= nums.length <= 10^5
0 <= nums[i] <= 10^9
Solution: count 1s
For 5 (101b), we can add 1s for 5 times which of cause isn’t the best way to generate 5, the optimal way is to [+1, *2, +1]. We have to add 1 for each 1 in the binary format. e.g. 11 (1011), we need 3x “+1” op, and 4 “*2” op. Fortunately, the “*2” can be shared/delayed, thus we just need to find the largest number.
e.g. [2,4,8,16]
[0, 0, 0, 0] -> [0, 0, 0, 1] -> [0, 0, 0, 2]
[0, 0, 0, 2] -> [0, 0, 1, 2] -> [0, 0, 2, 4]
[0, 0, 2, 4] -> [0, 1, 2, 4] -> [0, 2, 4, 8]
[0, 2, 4, 8] -> [1, 2, 4, 8] -> [2, 4, 8, 16]
ans = sum{count_1(arr_i)} + high_bit(max(arr_i))
Time complexity: O(n*log(max(arr_i))
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 |
class Solution { public: int minOperations(vector<int>& nums) { int ans = 0; int high = 0; for (int x : nums) { high = max(high, 31 - __builtin_clz(x | 1)); ans += std::bitset<32>(x).count(); } return ans + high; } }; |
Java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
class Solution { public int minOperations(int[] nums) { int ans = 0; int high = 0; for (int x : nums) { int l = -1; while (x != 0) { ans += x & 1; x >>= 1; ++l; } high = Math.max(high, l); } return ans + high; } } |
Python3
1 2 3 |
class Solution: def minOperations(self, nums: List[int]) -> int: return sum(bin(x).count('1') for x in nums) + len(bin(max(nums))) - 3 |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment