Minimum Numbers of Function Calls to Make Target Array

Minimum Numbers of Function Calls to Make Target Array - Problem

You are given an integer array target. 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 can call incrementByOne(arr, i): Increment the value of arr[i] by 1.
You can call doubleAll(arr): Double the value of each element in arr.

You want to use the modify function to convert arr to target using the minimum number of calls.

Return the minimum number of function calls to make target from arr.

The test cases are generated so that the answer fits in a 32-bit signed integer.

Input & Output

Example 1 — Basic Operations

$ Input: target = [1,5]

› Output: 5

💡 Note: To build [1,5]: Start with [0,0]. Increment arr[0] to get [1,0]. Increment arr[1] to get [1,1]. Double all to get [2,2]. Increment arr[1] to get [2,3]. Double all to get [4,6]. But this is wrong path. Optimal: increment operations = 1+2=3 (from binary 1=1₂, 5=101₂), double operations = max(0,2)=2. Total = 5.

Example 2 — Single Element

$ Input: target = [2]

› Output: 2

💡 Note: To build [2]: 2 in binary is 10₂. Need 1 increment operation (one 1-bit) and 1 double operation (bit at position 1). Total = 1 + 1 = 2.

Example 3 — All Zeros

$ Input: target = [0,0]

› Output: 0

💡 Note: Array is already [0,0], no operations needed.

Constraints

1 ≤ target.length ≤ 10⁵
0 ≤ target[i] ≤ 10⁹

Visualization

Tap to expand

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is that this is a bit manipulation problem in disguise. Each number's binary representation tells us exactly how many operations we need: the number of 1-bits equals increment operations, and the highest bit position across all numbers equals the maximum doubling operations needed. Best approach uses built-in bit functions. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Direct Bit Manipulation	O(n)	O(1)	Use built-in bit manipulation functions for optimal performance
Optimized Greedy with Global Doubling	O(n × log(max))	O(1)	Count individual increment operations and find maximum doubling operations needed
Simulation Approach	O(n × log(max))	O(1)	Simulate the reverse process for each number individually

Direct Bit Manipulation — Algorithm Steps

For each number, count 1-bits using built-in popcount
Find the highest bit position using bit length functions
Take maximum of all bit positions for global doubling operations
Return sum of all increment operations plus maximum doubling operations

Visualization

Tap to expand

Step-by-Step Walkthrough

Built-in Functions

Use popcount and bit length functions

Single Pass

Count bits and track maximum in one loop

Optimal Result

Sum increments + maximum doublings

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int popcount(unsigned int n) {
    return __builtin_popcount(n);
}

int clz(unsigned int n) {
    return __builtin_clz(n);
}

int solution(int* target, int targetSize) {
    if (targetSize == 0) return 0;
    
    int incrementOps = 0;
    int maxDoubleOps = 0;
    
    for (int i = 0; i < targetSize; i++) {
        int num = target[i];
        if (num == 0) continue;
        
        // Count 1-bits using built-in function
        incrementOps += popcount(num);
        
        // Find highest bit position using built-in function
        int doubleOps = 31 - clz(num);
        if (doubleOps > maxDoubleOps) {
            maxDoubleOps = doubleOps;
        }
    }
    
    return incrementOps + maxDoubleOps;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Simple array parsing
    int target[1000];
    int size = 0;
    
    char* ptr = strchr(line, '[');
    if (ptr) {
        ptr++;
        char* token = strtok(ptr, ",]");
        while (token && size < 1000) {
            target[size++] = atoi(token);
            token = strtok(NULL, ",]");
        }
    }
    
    int result = solution(target, size);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Built-in bit operations run in constant time for each number

✓ Linear Growth

Space Complexity

O(1)

Only using constant extra variables

✓ Linear Space

28.0K Views

Medium Frequency

~25 min Avg. Time

856 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Direct Bit Manipulation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler