1558. Minimum Numbers of Function Calls to Make Target Array LeetCode Solution

In this guide, you will get 1558. Minimum Numbers of Function Calls to Make Target Array LeetCode Solution with the best time and space complexity. The solution to Minimum Numbers of Function Calls to Make Target Array problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

  1. Problem Statement
  2. Complexity Analysis
  3. Minimum Numbers of Function Calls to Make Target Array solution in C++
  4. Minimum Numbers of Function Calls to Make Target Array solution in Java
  5. Minimum Numbers of Function Calls to Make Target Array solution in Python
  6. Additional Resources
1558. Minimum Numbers of Function Calls to Make Target Array LeetCode Solution image

Problem Statement of Minimum Numbers of Function Calls to Make Target Array

You are given an integer array nums. You have an integer array arr of the same length with all values set to 0 initially. You also have the following modify function:

You want to use the modify function to convert arr to nums using the minimum number of calls.
Return the minimum number of function calls to make nums from arr.
The test cases are generated so that the answer fits 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.

See also  3176. Find the Maximum Length of a Good Subsequence I LeetCode Solution

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).

Constraints:

1 <= nums.length <= 105
0 <= nums[i] <= 109

Complexity Analysis

  • Time Complexity: O(n)
  • Space Complexity: O(1)

1558. Minimum Numbers of Function Calls to Make Target Array LeetCode Solution in C++

class Solution {
 public:
  int minOperations(vector<int>& nums) {
    const int mx = ranges::max(nums);
    return accumulate(nums.begin(), nums.end(), 0,
                      [](int subtotal, unsigned num) {
      return subtotal + popcount(num);
    }) + (mx == 0 ? 0 : static_cast<int>(log2(mx)));
  }
};
/* code provided by PROGIEZ */

1558. Minimum Numbers of Function Calls to Make Target Array LeetCode Solution in Java

class Solution {
  public int minOperations(int[] nums) {
    final int mx = Arrays.stream(nums).max().getAsInt();
    return Arrays.stream(nums).map(num -> Integer.bitCount(num)).sum() +
        (mx == 0 ? 0 : (int) (Math.log(mx) / Math.log(2)));
  }
}
// code provided by PROGIEZ

1558. Minimum Numbers of Function Calls to Make Target Array LeetCode Solution in Python

class Solution:
  def minOperations(self, nums: list[int]) -> int:
    mx = max(nums)
    return (sum(num.bit_count() for num in nums) +
            (0 if mx == 0 else mx.bit_length() - 1))
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Similar: