We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Numbers of Function Calls to Make Target Array

Number: 1662

Difficulty: Medium

Paid? No

Companies: Amazon

Problem Description

Given an integer array nums, start from an array arr of the same length with all elements equal to zero. You can perform two types of operations: increment a single element by 1, and double all elements in arr. The goal is to convert arr into nums using the minimum number of operations.

Key Insights

  • Instead of building from 0 to nums, work in reverse by reducing nums to 0.
  • In reverse, a doubling is equivalent to halving all even numbers.
  • An increment in forward order corresponds to a decrement in reverse when the number is odd.
  • The minimum operations equal the sum of decrements (each one in binary representation corresponds to a needed increment) plus the maximal number of doublings (determined by the highest bit length among nums).

Space and Time Complexity

Time Complexity: O(n + log(m)) where n is the number of elements in nums and m is the maximum element value. Space Complexity: O(1)

Solution

The idea is to simulate the reverse process starting from the target array back to an array of zeros. For each number, if it is odd, reduce it by 1 (this reflects an increment in the forward direction). Once all numbers are even, divide the entire list by 2 (reflecting a doubling operation in forward order).
Alternatively, by analyzing the binary representation:

  • The number of 1-bits in nums gives the total number of decrement/increment operations needed.
  • The maximum bit-length among nums (minus one) gives the number of doubling operations needed. Summing these gives the minimal operations required.

Code Solutions

def minOperations(nums):
    operations = 0
    maxDoubling = 0  # To track the maximum number of doublings needed based on bit length
    
    for num in nums:
        countOnes = 0
        temp = num
        while temp:
            if temp & 1:
                countOnes += 1
            temp >>= 1
        operations += countOnes
        
        # Calculate the bit length of num
        maxDoubling = max(maxDoubling, num.bit_length())
    
    # Doubling operations occur once per bit shift, except for the last bit.
    if maxDoubling > 0:
        operations += (maxDoubling - 1)
    
    return operations

# Example test cases
print(minOperations([1, 5]))   # Output: 5
print(minOperations([2, 2]))   # Output: 3
print(minOperations([4, 2, 5]))   # Output: 6
← Back to All Questions