LeetCode 1558 - Minimum Numbers of Function Calls to Make Target Array

This problem asks us to transform an initial array arr of zeros into a target array nums using a minimal number of operations. There are two allowed operations: incrementing any single element of the array by 1, or doubling all elements of the array.

leetcodemediumarraygreedybit-manipulation

LeetCode Problem 1558

Difficulty: 🟡 Medium
Topics: Array, Greedy, Bit Manipulation

Solution

Problem Understanding

This problem asks us to transform an initial array arr of zeros into a target array nums using a minimal number of operations. There are two allowed operations: incrementing any single element of the array by 1, or doubling all elements of the array. The goal is to count the minimum total operations required to reach nums.

The input nums is an integer array with length up to 10^5, and each element can be as large as 10^9. The output is a single integer representing the minimal number of function calls. Edge cases include elements being zero, arrays with all equal values, or arrays with very large values that require many doublings.

The problem guarantees that the answer fits in a 32-bit signed integer, so we do not need to worry about integer overflow.

Key points to note are that doubling affects all elements simultaneously, and incrementing affects individual elements. This implies that a naive approach that simulates every operation from 0 to nums[i] would be too slow.

Approaches

The brute-force approach would simulate the process directly: repeatedly check which elements need incrementing and when to apply a doubling operation. For each doubling, we would double all non-zero elements and increment others individually. This would work correctly but is highly inefficient for large numbers because we could perform up to 10^9 operations per element, resulting in O(n * max(nums)) time complexity.

The key insight for the optimal solution is to work backwards using bit manipulation. Each increment operation corresponds to setting a bit in the binary representation of the number. Each doubling operation corresponds to a left shift in binary. Therefore, counting the number of 1s in the binary representation of each number gives the number of increments, and the highest bit position across all numbers gives the number of doublings needed. This approach is efficient and works in O(n log max(nums)) time.

Approach Time Complexity Space Complexity Notes
Brute Force O(n * max(nums)) O(n) Simulates every operation, too slow for large nums
Optimal O(n log max(nums)) O(1) Uses bit manipulation to count increments and doublings efficiently

Algorithm Walkthrough

  1. Initialize two counters: increments to count the number of increment operations, and doublings to count the number of doubling operations.
  2. Iterate through each element num in nums.
  3. For each num, convert it to binary. Count the number of 1 bits and add to increments.
  4. Track the maximum bit length among all numbers, which represents the number of doubling operations needed. Subtract one because the highest bit corresponds to the number of doublings (a single element 1 requires 0 doublings).
  5. Return the total operations as the sum of increments and doublings.

Why it works: Each 1 in the binary representation corresponds to a necessary increment operation at that bit level. Doubling corresponds to shifting the current value to the left, so the highest set bit determines how many doublings are needed to reach the largest number. This method guarantees the minimal operations because it separates operations optimally per bit.

Python Solution

from typing import List

class Solution:
    def minOperations(self, nums: List[int]) -> int:
        increments = 0
        max_bits = 0
        
        for num in nums:
            bits = 0
            temp = num
            while temp > 0:
                if temp & 1:
                    increments += 1
                temp >>= 1
                bits += 1
            max_bits = max(max_bits, bits)
        
        doublings = max_bits - 1 if max_bits > 0 else 0
        return increments + doublings

The implementation iterates through each number, using bitwise operations to count 1s (increments) and the total number of bits (doublings). We keep a running maximum of bit lengths to determine the required doublings for the largest number.

Go Solution

func minOperations(nums []int) int {
    increments := 0
    maxBits := 0
    
    for _, num := range nums {
        bits := 0
        temp := num
        for temp > 0 {
            if temp&1 == 1 {
                increments++
            }
            temp >>= 1
            bits++
        }
        if bits > maxBits {
            maxBits = bits
        }
    }
    
    doublings := 0
    if maxBits > 0 {
        doublings = maxBits - 1
    }
    
    return increments + doublings
}

The Go implementation mirrors the Python logic. We use bitwise operations to count increments and bit length. Go handles large integers similarly to Python, and slices replace arrays for iteration.

Worked Examples

Example 1: nums = [1,5]

num Binary Increments Doublings
1 1 1 1
5 101 2 3

Total increments = 1 + 2 = 3

Maximum bit length = 3 → doublings = 3 - 1 = 2

Total operations = 3 + 2 = 5

Example 2: nums = [2,2]

num Binary Increments Doublings
2 10 1 2
2 10 1 2

Total increments = 2

Maximum bit length = 2 → doublings = 2 - 1 = 1

Total operations = 2 + 1 = 3

Example 3: nums = [4,2,5]

num Binary Increments Doublings
4 100 1 3
2 10 1 2
5 101 2 3

Total increments = 1 + 1 + 2 = 4

Maximum bit length = 3 → doublings = 3 - 1 = 2

Total operations = 4 + 2 = 6

Complexity Analysis

Measure Complexity Explanation
Time O(n log max(nums)) Iterates through each number and examines each bit (up to 30 bits for 10^9)
Space O(1) Only counters and temporary variables are used, no extra structures

We efficiently process all numbers using bitwise operations, ensuring the algorithm scales to large inputs.

Test Cases

# Provided examples
assert Solution().minOperations([1,5]) == 5  # mixed increments and doublings
assert Solution().minOperations([2,2]) == 3  # identical numbers
assert Solution().minOperations([4,2,5]) == 6  # larger array

# Edge cases
assert Solution().minOperations([0]) == 0  # zero requires no operations
assert Solution().minOperations([1]) == 1  # single increment
assert Solution().minOperations([1024]) == 11  # powers of two, only doublings and one increment
assert Solution().minOperations([0,1,2,3]) == 5  # mixed small numbers
assert Solution().minOperations([10**9]) == 30  # large number max value for 32-bit
Test Why
[1,5] Validates multiple increments and doublings
[2,2] Checks behavior with equal numbers
[4,2,5] Checks handling of mixed sizes and bit lengths
[0] Minimal edge case with zero
[1] Minimal non-zero case
[1024] Power of two, tests doubling sequence
[0,1,2,3] Small mixed numbers, verifies incremental logic
[10^9] Large number, stress test for bit counting

Edge Cases

The first important edge case is when all elements are zero. This tests whether the implementation can correctly handle no operations. Our algorithm counts bits, so zero contributes nothing to increments or doublings, returning zero.

The second edge case is when the array contains a single element. This ensures the algorithm handles minimal input length without errors. The algorithm works as expected because it iterates over one element, counting its binary bits.

The third edge case is when the elements are large powers of two. In this case, only doublings are needed, with exactly one increment if the power of two is greater than 1. The algorithm correctly calculates doublings using the highest bit and increments from the binary representation. This confirms correctness for large numbers and verifies no overflow occurs.