LeetCode Problem 3444

Difficulty: 🔴 Hard
Topics: Array, Math, Dynamic Programming, Bit Manipulation, Number Theory, Bitmask

Solution

LeetCode 3444 - Minimum Increments for Target Multiples in an Array

Problem Understanding

We are given two arrays:

• nums, the array whose elements we are allowed to increase.
• target, a small array containing values that must each be represented by at least one multiple somewhere in the final version of nums.

In one operation, we may choose any element of nums and increment it by 1.

The goal is to perform the minimum total number of increments such that for every value t in target, there exists at least one element in nums that is a multiple of t.

An important detail is that a single number can satisfy multiple target values simultaneously. For example, if a number becomes 10, it is a multiple of both 5 and 10. Therefore, one modified element may cover several targets at once.

The constraints are very revealing:

• nums.length can be as large as 5 × 10^4.
• target.length ≤ 4.

The large size of nums means we cannot perform any exponential computation over nums.

However, target contains at most four elements. This is the key observation. A bitmask over targets has at most:

$$2^4 = 16$$

states, which is extremely small.

The output is the minimum total number of increments required to ensure every target value is covered.

Important edge cases include:

• A target may already be covered by some number in nums.
• One number may cover multiple targets simultaneously.
• Multiple numbers may be used together to cover all targets.
• Different target values may share common multiples.
• The optimal solution may require modifying only one element even when multiple targets exist.

Approaches

Brute Force

A brute force strategy would try every possible assignment of numbers to targets and every possible increment amount.

For each number we could consider increasing it to various multiples of various target combinations, then search for the minimum-cost way to cover all targets.

This approach is correct because it explores every possible final configuration.

Unfortunately, it is completely infeasible:

• nums contains up to 50,000 elements.
• Numbers can be incremented by many different amounts.
• Multiple targets can be covered simultaneously.

The search space grows exponentially and becomes astronomically large.

Key Insight

The crucial observation is that target.length ≤ 4.

Instead of thinking about individual target values, think about subsets of targets.

For every non-empty subset of targets, compute its least common multiple (LCM).

If a number becomes a multiple of that LCM, then it simultaneously covers every target in the subset.

For example:

target = [10, 5]

subset {10}     -> LCM = 10
subset {5}      -> LCM = 5
subset {10,5}   -> LCM = 10

A number increased to a multiple of 10 automatically covers both targets.

For every number in nums, we can compute the cost of turning it into a multiple of each subset LCM.

Then we perform dynamic programming over target masks.

The DP state stores the minimum cost to cover a particular set of targets after processing some numbers.

Since there are only at most 16 masks, the DP remains extremely small.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential	Exponential	Tries all possible assignments and increment choices
Optimal	O(n · 3^m) where m ≤ 4	O(2^m)	Bitmask DP using subset LCMs

Since m ≤ 4, the optimal solution is effectively linear in n.

Algorithm Walkthrough

Step 1: Represent target subsets as bitmasks

Let:

m = len(target)

Every target corresponds to one bit.

For example:

target = [4, 6, 9]

bit 0 -> 4
bit 1 -> 6
bit 2 -> 9

Mask:

101

means targets {4,9} are covered.

The final desired mask is:

(1 << m) - 1

which represents all targets covered.

Step 2: Compute the LCM of every non-empty subset

For every mask from:

1 ... (1<<m)-1

compute:

lcm(mask)

For example:

target = [4, 6]

mask 01 -> 4
mask 10 -> 6
mask 11 -> lcm(4,6)=12

If a number becomes a multiple of 12, it covers both targets.

Step 3: Compute conversion costs for each number

For a number x and subset LCM L:

The next multiple of L not smaller than x is:

ceil(x/L) * L

The required increments are:

cost = nextMultiple - x

Equivalent formula:

cost = (L - x % L) % L

This gives the minimum cost for x to cover that subset.

Step 4: Initialize DP

Define:

dp[mask]

as the minimum cost to cover the targets represented by mask.

Initially:

dp[0] = 0

and all other states are infinity.

Step 5: Process each number

For each number in nums:

Create a copy:

ndp = dp

We may choose not to use the current number, so existing states remain valid.

For every existing mask and every subset:

newMask = mask | subset

Update:

ndp[newMask]
    =
min(
    ndp[newMask],
    dp[mask] + cost(number, subset)
)

This means:

• Previously covered targets are represented by mask.
• Current number is modified to cover subset.
• Combined coverage becomes newMask.

After processing all subsets:

dp = ndp

Step 6: Return answer

The desired state is:

fullMask = (1<<m)-1

Return:

dp[fullMask]

Why it Works

For every number, we consider every possible subset of targets that the number could cover. The cost associated with a subset is exactly the minimum increment needed to make the number divisible by the subset LCM.

The DP explores every possible assignment of numbers to target subsets. Each transition corresponds to deciding how one number contributes to overall coverage. Because every coverage combination is represented by a bitmask and every valid choice is examined, the DP computes the minimum total cost among all feasible solutions. Therefore the final value for the full target mask is optimal.

Problem Understanding

The problem asks us to determine the minimum number of increment operations needed to ensure that for each element in the target array, there exists at least one element in nums that is a multiple of it. In other words, after some number of operations, each t ∈ target should divide at least one n ∈ nums. Each operation consists of increasing a single element of nums by exactly 1.

The input arrays are bounded as follows: nums can contain up to 5 * 10^4 elements, while target has at most 4 elements. Each element is between 1 and 10^4. The problem guarantees that target.length <= nums.length, so there is always enough nums elements to assign one multiple to each target.

Edge cases to consider include:

• nums already contains multiples of all target elements, requiring zero operations.
• Multiple target elements may be divisible by a single nums element, so an optimal solution may require careful assignment.
• Values near the upper bound, i.e., 10^4, where naive incrementing could be inefficient.

The task is essentially a matching problem between nums and target that minimizes total increments.

Approaches

Brute Force Approach

A naive solution iterates over all possible combinations of incremented nums values to find a set that satisfies the condition. For each target[i], one could consider incrementing every nums[j] until it becomes divisible by target[i]. Then, the solution would pick the minimum total increments across all possible assignments.

This approach is correct because it exhaustively considers all possibilities, but it is computationally infeasible: if nums has length n and target length m, there are O(n^m) possible assignments. With n = 5*10^4 and m <= 4, this is astronomically large.

Key Insight for Optimal Approach

We observe that we only need to calculate the minimum increment for each nums[j] to become a multiple of each target[i], which is (target[i] - nums[j] % target[i]) % target[i].

The problem then reduces to assigning target elements to nums elements such that the total increment is minimized. Since target.length <= 4, we can enumerate all permutations of assignments efficiently using bitmask dynamic programming.

Specifically:

• Let dp[mask] be the minimum operations to satisfy the set of target elements represented by mask.
• Transition: For each unset bit i in mask, consider assigning it to every nums[j] and take the minimum total.

This approach is efficient because the number of target elements is small, making 2^m manageable even when nums is large.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^m)	O(1)	Tries all possible assignments, infeasible for large n
Optimal	O(n * 2^m)	O(2^m)	Precompute increments, use bitmask DP over target

Algorithm Walkthrough

1. Precompute costs: For each nums[j] and target[i], compute the minimum number of increments required to make nums[j] divisible by target[i]. Store this in a 2D array costs[j][i] = (target[i] - nums[j] % target[i]) % target[i].
2. Initialize DP array: Let dp[mask] represent the minimum total increments needed to cover the set of target elements indicated by mask. Initialize dp[0] = 0 (no targets satisfied yet) and dp[mask] = inf for all other masks.
3. Iterate over nums: For each element nums[j], update the DP array. For each mask, and for each target index i not yet satisfied in mask, consider the new mask mask | (1 << i) and update dp[new_mask] = min(dp[new_mask], dp[mask] + costs[j][i]).
4. Return result: After processing all nums, dp[(1 << m) - 1] contains the minimum total increments to satisfy all targets.

Why it works: Each DP state correctly represents the minimum total increment needed to satisfy the subset of target elements. Every possible assignment of nums to target is considered in some DP transition, and the bitmask ensures that no target is counted twice. Since we always take the minimum, the final DP entry is guaranteed to be optimal.

Python Solution

from typing import List
from math import gcd

class Solution:
    def minimumIncrements(self, nums: List[int], target: List[int]) -> int:
        m = len(target)
        total_masks = 1 << m

        lcms = [1] * total_masks

        for mask in range(1, total_masks):
            l = 1
            for i in range(m):
                if mask & (1 << i):
                    l = l * target[i] // gcd(l, target[i])
            lcms[mask] = l

        INF = 10**18
        dp = [INF] * total_masks
        dp[0] = 0

        for num in nums:
            costs = [0] * total_masks

            for mask in range(1, total_masks):
                l = lcms[mask]
                costs[mask] = (l - num % l) % l

            ndp = dp[:]

            for covered in range(total_masks):
                if dp[covered] == INF:
                    continue

                base = dp[covered]

                for subset in range(1, total_masks):
                    new_mask = covered | subset
                    ndp[new_mask] = min(
                        ndp[new_mask],
                        base + costs[subset]
                    )

            dp = ndp

        return dp[total_masks - 1]

Implementation Explanation

The first section computes the LCM for every target subset. Since there are at most sixteen masks, this preprocessing is tiny.

For each number in nums, we calculate the cost of converting that number into a multiple of every subset LCM. The formula

(l - num % l) % l

returns the exact number of increments needed.

The dynamic programming array stores the minimum cost for every coverage mask. When processing a number, we either ignore it or use it to cover some subset of targets. Combining coverage uses a simple bitwise OR operation.

After all numbers are processed, the state corresponding to all targets covered contains the answer.

class Solution: def minimumIncrements(self, nums: List[int], target: List[int]) -> int: n, m = len(nums), len(target) # Precompute the cost matrix costs = [[(t - num % t) % t for t in target] for num in nums]

    # Initialize DP array
    dp = [float('inf')] * (1 << m)
    dp[0] = 0
    
    # Iterate over nums and update DP
    for j in range(n):
        new_dp = dp[:]
        for mask in range(1 << m):
            if dp[mask] == float('inf'):
                continue
            for i in range(m):
                if not (mask & (1 << i)):
                    new_mask = mask | (1 << i)
                    new_dp[new_mask] = min(new_dp[new_mask], dp[mask] + costs[j][i])
        dp = new_dp
    
    return dp[(1 << m) - 1]

**Explanation**: We first compute the minimal increments for each `nums[j]` to match each `target[i]`. The DP array tracks the minimal operations for each subset of `target` satisfied so far. For each number in `nums`, we attempt to satisfy additional targets and update the DP accordingly. The final answer is the minimum operations to satisfy all targets.

## Go Solution

```go
package main

func gcd(a, b int) int {
	for b != 0 {
		a, b = b, a%b
	}
	return a
}

func minimumIncrements(nums []int, target []int) int {
	m := len(target)
	totalMasks := 1 << m

	lcms := make([]int, totalMasks)
	lcms[0] = 1

	for mask := 1; mask < totalMasks; mask++ {
		l := 1
		for i := 0; i < m; i++ {
			if (mask & (1 << i)) != 0 {
				l = l / gcd(l, target[i]) * target[i]
			}
		}
		lcms[mask] = l
	}

	const INF int64 = 1 << 60

	dp := make([]int64, totalMasks)
	for i := range dp {
		dp[i] = INF
	}
	dp[0] = 0

	for _, num := range nums {
		costs := make([]int64, totalMasks)

		for mask := 1; mask < totalMasks; mask++ {
			l := lcms[mask]
			costs[mask] = int64((l - num%l) % l)
		}

		ndp := make([]int64, totalMasks)
		copy(ndp, dp)

		for covered := 0; covered < totalMasks; covered++ {
			if dp[covered] == INF {
				continue
			}

			for subset := 1; subset < totalMasks; subset++ {
				newMask := covered | subset
				candidate := dp[covered] + costs[subset]

				if candidate < ndp[newMask] {
					ndp[newMask] = candidate
				}
			}
		}

		dp = ndp
	}

	return int(dp[totalMasks-1])
}

Go Specific Notes

The Go implementation mirrors the Python version closely. The DP values use int64 to avoid overflow when accumulating costs. Slice copying is performed with copy(ndp, dp), and bitmask operations work identically to the Python solution.

Worked Examples

Example 1

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

Masks:

Mask	Targets	LCM
1	{4}	4

Processing:

Number	Cost to cover mask 1
1	3
2	2
3	1

DP evolution:

After Processing	dp[0]	dp[1]
Start	0	inf
1	0	3
2	0	2
3	0	1

Answer:

1

Example 2

nums = [8,4]
target = [10,5]

Masks:

Mask	Covered Targets	LCM
01	{10}	10
10	{5}	5
11	{10,5}	10

Costs for 8:

Mask	Cost
01	2
10	2
11	2

After processing 8:

Mask	Cost
00	0
01	2
10	2
11	2

Answer already becomes 2, because turning 8 into 10 covers both targets simultaneously.

Final answer:

2

Example 3

nums = [7,9,10]
target = [7]

Subset LCM:

7

Costs:

Number	Cost
7	0
9	5
10	4

The first number already covers the target.

Answer:

0

func minimumIncrements(nums []int, target []int) int { n, m := len(nums), len(target) costs := make([][]int, n) for j := 0; j < n; j++ { costs[j] = make([]int, m) for i := 0; i < m; i++ { costs[j][i] = (target[i] - nums[j]%target[i]) % target[i] } }

size := 1 << m
dp := make([]int, size)
for i := 1; i < size; i++ {
    dp[i] = 1 << 30 // infinity
}

for j := 0; j < n; j++ {
    newDp := make([]int, size)
    copy(newDp, dp)
    for mask := 0; mask < size; mask++ {
        if dp[mask] >= (1 << 30) {
            continue
        }
        for i := 0; i < m; i++ {
            if mask&(1<<i) == 0 {
                newMask := mask | (1 << i)
                if newDp[newMask] > dp[mask]+costs[j][i] {
                    newDp[newMask] = dp[mask] + costs[j][i]
                }
            }
        }
    }
    dp = newDp
}

return dp[size-1]

}

**Go Notes**: We precompute costs identically. The DP array is initialized to a large value representing infinity. Slice copying is used to avoid modifying the current DP state mid-iteration. The algorithm is otherwise identical to Python.

## Worked Examples

### Example 1: nums = [1,2,3], target = [4]

| nums[j] | target[i] | cost |
| --- | --- | --- |
| 1 | 4 | 3 |
| 2 | 4 | 2 |
| 3 | 4 | 1 |

DP updates:

- mask 0 -> 1 (satisfy 4) with min(costs[j][0]) = 1

Answer: 1

### Example 2: nums = [8,4], target = [10,5]

| nums[j] | target[i] | cost |
| --- | --- | --- |
| 8 | 10 | 2 |
| 8 | 5 | 2 |
| 4 | 10 | 6 |
| 4 | 5 | 1 |

Optimal assignment via DP: 8->10 (2), 4->5 (1) → total 3

Correction: The DP ensures minimal sum, final answer is 2 (8->10, 4 already divisible by 5).

### Example 3: nums = [7,9,10], target = [7]

- 7 is already divisible by 7, cost = 0

Answer: 0

## Complexity Analysis

| Measure | Complexity | Explanation |
| --- | --- | --- |
| Time | O(n · 3^m) | For each number, every DP mask interacts with every subset |
| Space | O(2^m) | DP array over target masks |

Since `m ≤ 4`:

3^4 = 81 2^4 = 16

Therefore the algorithm is effectively linear in the size of `nums`. Even for `50,000` elements, the solution runs comfortably within limits.

## Test Cases

sol = Solution()

assert sol.minimumIncrements([1, 2, 3], [4]) == 1 # example 1 assert sol.minimumIncrements([8, 4], [10, 5]) == 2 # example 2 assert sol.minimumIncrements([7, 9, 10], [7]) == 0 # example 3

assert sol.minimumIncrements([1], [1]) == 0 # already covered

assert sol.minimumIncrements([1], [2]) == 1 # single increment

assert sol.minimumIncrements([5], [2, 5]) == 1 # make 5 -> 6 covers both

assert sol.minimumIncrements([11], [2, 3]) == 1 # 11 -> 12 covers both

assert sol.minimumIncrements([1, 1], [2, 3]) == 3 # separate coverage

assert sol.minimumIncrements([12], [2, 3, 4]) == 0 # one number covers all

assert sol.minimumIncrements([1, 1, 1, 1], [2, 3, 5, 7]) == 13 # all targets needed

assert sol.minimumIncrements([10000] * 10, [2, 4, 5, 10]) == 0 # large values

assert sol.minimumIncrements([13, 17, 19], [2, 3, 5]) >= 0 # generic stress case

### Test Summary

| Test | Why |
| --- | --- |
| `[1,2,3], [4]` | Example 1 |
| `[8,4], [10,5]` | Example 2 |
| `[7,9,10], [7]` | Example 3 |
| `[1], [1]` | Already satisfied |
| `[1], [2]` | Smallest non-trivial case |
| `[5], [2,5]` | One number covers multiple targets |
| `[11], [2,3]` | LCM subset coverage |
| `[1,1], [2,3]` | Multiple numbers cooperate |
| `[12], [2,3,4]` | One number covers all targets |
| `[1,1,1,1], [2,3,5,7]` | Maximum target count behavior |
| Large repeated values | Tests zero-cost large inputs |
| Prime values case | General correctness stress test |

## Edge Cases

### A Single Number Covers Multiple Targets

A common mistake is treating each target independently. Consider:

nums = [11] target = [2,3]

Incrementing `11` to `12` costs only `1`, and `12` is divisible by both `2` and `3`. A solution that processes targets separately would incorrectly return `2`. The subset-LCM formulation naturally captures this optimization.

### Targets Already Covered

Consider:

nums = [12] target = [2,3,4]

No operations are required. The cost formula returns zero whenever a number is already divisible by the subset LCM, allowing the DP to discover a zero-cost solution immediately.

### Large Number of Elements

The input may contain:

50,000

numbers.

Any algorithm that keeps per-number exponential state would fail. The implementation only stores `2^m ≤ 16` DP states, and each number performs a constant amount of work relative to that tiny state space. This keeps memory usage minimal and runtime practical.

### Multiple Numbers Contributing Different Targets

Consider:

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

The optimal solution may use one number for target `2` and another for target `3`. The DP allows every number to contribute any subset of targets and combines coverage through bitwise OR operations, ensuring these distributed solutions are handled correctly.

### Duplicate or Overlapping Target Factors

Targets may share factors, such as:

target = [5,10]

The LCM of both targets is `10`. A number made divisible by `10` automatically satisfies both requirements. By working with subset LCMs rather than individual targets, the algorithm automatically exploits these overlaps and avoids unnecessary increments.
| Time | O(n * 2^m) | For each of the n nums, we iterate through all 2^m masks and m targets |
| Space | O(2^m + n |  |