Minimum Increments for Target Multiples in an Array

Minimum Increments for Target Multiples in an Array - Problem

Array Math Dynamic Programming Bit Manipulation Number Theory Bitmask Hard

You are given two arrays, nums and target. In a single operation, you may increment any element of nums by 1.

Return the minimum number of operations required so that each element in target has at least one multiple in nums.

A multiple of a number x is any number that can be expressed as k * x where k is a positive integer.

Input & Output

Example 1 — Basic Case

$ Input: nums = [1,2,3], target = [2,4]

› Output: 3

💡 Note: Assign nums[0]=1 to target[0]=2: cost 2-1=1 to make 1→2. Assign nums[1]=2 to target[1]=4: cost 4-2=2 to make 2→4. Total cost: 1+2=3.

Example 2 — Zero Elements

$ Input: nums = [0,0,0], target = [1,2,3]

› Output: 6

💡 Note: Transform 0→1 (cost 1), 0→2 (cost 2), 0→3 (cost 3). Total cost: 1+2+3=6.

Example 3 — Multiple Assignment

$ Input: nums = [3,5], target = [2,4]

› Output: 1

💡 Note: Assign nums[0]=3 to target[1]=4: cost 4-3=1. Assign nums[1]=5 to target[0]=2: 5 is already multiple of 2 (5=2×2.5), but we need integer multiples, so 5→6 costs 1, then 6→8 costs 2, giving 6=2×3. Actually, 5→4 costs -1 which is impossible. We need 5→6→8→10→... The first multiple ≥5 is 6=2×3, cost 1. Wait, 5 to get multiple of 2: need k×2≥5, so k≥2.5, k=3, so 6. Cost=6-5=1. Total: assign nums[1]=5 to target[0]=2 costs 1, nums[0]=3 to target[1]=4 costs 1. Total=2. But optimal is nums[0]=3→target[0]=2 (cost 0, since 3 is not multiple of 2, need 4=2×2, cost 1), nums[1]=5→target[1]=4 (cost 0, since need 8=4×2, cost 3). Let me recalculate: 3→multiple of 2: need 4, cost 1. 5→multiple of 4: need 8, cost 3. Total 4. Alternative: 3→multiple of 4: need 4, cost 1. 5→multiple of 2: need 6, cost 1. Total 2. So minimum is 2.

Constraints

1 ≤ nums.length, target.length ≤ 8
1 ≤ nums[i], target[i] ≤ 100

Visualization

Tap to expand

Understanding the Visualization

Input Arrays

nums=[1,2,3] and target=[2,4]

Assignment

Find optimal assignment of nums to targets

Calculate Cost

Sum increment costs for each assignment

Key Takeaway

🎯 Key Insight: Find the minimum cost bipartite matching between nums and target elements

Asked in

G Google 15 M Microsoft 12 a Amazon 8

The key insight is to find the minimum cost assignment where each target element gets exactly one multiple from nums. The optimal approach uses dynamic programming with bitmasks to track which targets are covered. Time: O(2^n × n × m), Space: O(2^n).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force with Recursion	O(n! × m)	O(n)	Try all possible assignments of nums elements to target elements
Dynamic Programming with Bitmask	O(2^n × n × m)	O(2^n)	Use bitmask DP to track which targets are covered and find minimum cost

Brute Force with Recursion — Algorithm Steps

For each target element, try assigning each available nums element
Calculate cost to make nums[i] a multiple of target[j]
Recursively solve for remaining targets
Return minimum cost across all assignments

Visualization

Tap to expand

Step-by-Step Walkthrough

Assignment

Try assigning each nums element to each target

Cost Calculation

Calculate increment cost for each assignment

Recursion

Recursively solve remaining assignments

Code -

solution.c — C

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

int backtrack(int* target, int targetSize, int targetIdx, int* used, int* nums, int numsSize) {
    if (targetIdx == targetSize) {
        return 0;
    }
    
    int minCost = INT_MAX;
    for (int i = 0; i < numsSize; i++) {
        if (used[i]) continue;
        
        int t = target[targetIdx];
        int n = nums[i];
        int cost;
        if (n == 0) {
            cost = t;
        } else {
            int k = (n + t - 1) / t;
            cost = k * t - n;
        }
        
        used[i] = 1;
        int totalCost = cost + backtrack(target, targetSize, targetIdx + 1, used, nums, numsSize);
        if (totalCost < minCost) {
            minCost = totalCost;
        }
        used[i] = 0;
    }
    
    return minCost;
}

int solution(int* nums, int numsSize, int* target, int targetSize) {
    int* used = (int*)calloc(numsSize, sizeof(int));
    int result = backtrack(target, targetSize, 0, used, nums, numsSize);
    free(used);
    return result;
}

int main() {
    int nums[100], target[100];
    int numsSize = 0, targetSize = 0;
    
    // Simple parsing for arrays
    char line[1000];
    fgets(line, sizeof(line), stdin);
    char* ptr = strtok(line, "[],\n");
    while (ptr != NULL) {
        nums[numsSize++] = atoi(ptr);
        ptr = strtok(NULL, "[],\n");
    }
    
    fgets(line, sizeof(line), stdin);
    ptr = strtok(line, "[],\n");
    while (ptr != NULL) {
        target[targetSize++] = atoi(ptr);
        ptr = strtok(NULL, "[],\n");
    }
    
    printf("%d\n", solution(nums, numsSize, target, targetSize));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n! × m)

n! permutations of assignments times m cost calculations

⚠ Quadratic Growth

Space Complexity

O(n)

Recursion stack depth of n target elements

⚡ Linearithmic Space

8.5K Views

Medium Frequency

~35 min Avg. Time

245 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

Brute Force with Recursion — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler