# Minimum Increments for Target Multiples in an Array
**Difficulty:** HARD
[External](https://leetcode.com/problems/minimum-increments-for-target-multiples-in-an-array)
Canonical: https://scaleengineer.com/dsa/problems/minimum-increments-for-target-multiples-in-an-array
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation), [Number Theory](https://scaleengineer.com/dsa/patterns/number-theory), [Bitmask](https://scaleengineer.com/dsa/patterns/bitmask)
**Data structures:** Array
---
## Problem
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`.

**Example 1:**

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

**Output:** 1

**Explanation:**

The minimum number of operations required to satisfy the condition is 1.

* Increment 3 to 4 with just one operation, making 4 a multiple of itself.

**Example 2:**

**Input:** nums = \[8,4\], target = \[10,5\]

**Output:** 2

**Explanation:**

The minimum number of operations required to satisfy the condition is 2.

* Increment 8 to 10 with 2 operations, making 10 a multiple of both 5 and 10.

**Example 3:**

**Input:** nums = \[7,9,10\], target = \[7\]

**Output:** 0

**Explanation:**

Target 7 already has a multiple in nums, so no additional operations are needed.

**Constraints:**

* `1 <= nums.length <= 5 * 104`
* `1 <= target.length <= 4`
* `target.length <= nums.length`
* `1 <= nums[i], target[i] <= 104`

# Approaches
## Brute-Force Recursion
A brute-force approach systematically explores every possible assignment of `nums` elements to cover subsets of `target` elements. This can be formulated as a recursive backtracking algorithm. For each number in `nums`, we decide whether to use it to cover a specific subset of the yet-unsatisfied targets or to not use it at all. This process continues until all targets are covered or all numbers from `nums` have been considered.
**Time:** O((2^k)^N), where N is `nums.length` and k is `target.length`. For each of the N numbers, we can choose to use it for any of the `2^k-1` subsets of targets or not use it, leading to roughly `2^k` choices per number. This is prohibitively slow. · **Space:** O(N) for the recursion stack depth, where N is the length of `nums`.
**Pros:** Conceptually simple and follows a natural decision-making process.
**Cons:** Extremely inefficient due to the massive number of redundant computations for the same subproblems (`index`, `mask`).; Guaranteed to receive a 'Time Limit Exceeded' (TLE) verdict on any reasonably large test case.
### Explanation
The core of this method is a recursive function that builds a solution step-by-step. The state of the recursion is typically defined by `(index, mask)`, where `index` tracks the current element in `nums` being considered, and `mask` is a bitmask indicating which `target` elements have been satisfied.

At each step `index`, the function branches out. One branch corresponds to skipping `nums[index]`. The other branches correspond to using `nums[index]` to satisfy any combination of the remaining targets. This creates a vast search tree of possibilities. The cost for using `nums[index]` to satisfy a set of targets is the number of increments required to make it a common multiple of them. The final answer is the minimum cost found across all paths in the search tree that successfully cover all targets.

```java
import java.util.Arrays;

class Solution {
    private int[] target;
    private int k;
    private long[][] memo;
    private long[] lcmOfMask;

    public int minimumValueSum(int[] nums, int[] target) {
        this.target = target;
        this.k = target.length;
        this.memo = new long[nums.length][1 << k];
        for (long[] row : memo) {
            Arrays.fill(row, -1);
        }

        // Precompute LCMs for all masks
        this.lcmOfMask = new long[1 << k];
        for (int mask = 1; mask < (1 << k); mask++) {
            long currentLcm = 1;
            for (int i = 0; i < k; i++) {
                if ((mask & (1 << i)) != 0) {
                    currentLcm = lcm(currentLcm, this.target[i]);
                }
            }
            lcmOfMask[mask] = currentLcm;
        }

        long result = solve(nums, 0, 0);
        return result >= Long.MAX_VALUE / 2 ? -1 : (int) result; // Assuming -1 for impossible
    }

    private long solve(int[] nums, int index, int mask) {
        if (mask == (1 << k) - 1) {
            return 0;
        }
        if (index == nums.length) {
            return Long.MAX_VALUE / 2; // Represents infinity
        }

        // This is the unmemoized version. With memoization, it becomes the DP approach.
        // if (memo[index][mask] != -1) {
        //     return memo[index][mask];
        // }

        // Choice 1: Skip nums[index]
        long minCost = solve(nums, index + 1, mask);

        // Choice 2: Use nums[index] to cover a subset of remaining targets
        int uncoveredMask = ((1 << k) - 1) & ~mask;
        for (int submask = uncoveredMask; submask > 0; submask = (submask - 1) & uncoveredMask) {
            long l = lcmOfMask[submask];
            long currentNum = nums[index];
            long cost = (l - (currentNum % l)) % l;
            
            long remainingCost = solve(nums, index + 1, mask | submask);
            if (remainingCost < Long.MAX_VALUE / 2) {
                minCost = Math.min(minCost, cost + remainingCost);
            }
        }

        // return memo[index][mask] = minCost;
        return minCost;
    }

    private long gcd(long a, long b) {
        while (b > 0) {
            long temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }

    private long lcm(long a, long b) {
        if (a == 0 || b == 0) return 0;
        return Math.abs(a * b) / gcd(a, b);
    }
}
```
### Algorithm
- Define a recursive function, say `solve(index, mask)`, which returns the minimum cost to satisfy the targets represented by the bits not set in `mask`, using numbers from `nums[index]` onwards.
- The `mask` is a bitmask of length `k` (where `k` is `target.length`), representing the subset of satisfied `target` elements.
- **Base Cases:**
  - If `mask` has all `k` bits set, all targets are satisfied. Return 0.
  - If `index` reaches the end of `nums` but `mask` is not yet full, it's impossible to satisfy the remaining targets. Return a very large value (infinity).
- **Recursive Step:** For the number `nums[index]`, we have several choices:
  1. **Skip `nums[index]`:** Don't use it. The cost is `solve(index + 1, mask)`.
  2. **Use `nums[index]`:** Use it to satisfy a non-empty subset of the currently unsatisfied targets. Iterate through all non-empty submasks `submask` of the `uncovered_targets`.
     - Calculate the cost to make `nums[index]` a common multiple of all targets in `submask`. This requires finding the least common multiple (LCM) of these targets, let's call it `L`. The cost is `(L - (nums[index] % L)) % L`.
     - The total cost for this choice is this calculated cost plus the result of the recursive call `solve(index + 1, mask | submask)`.
- The function returns the minimum cost found among all possible choices.

## Dynamic Programming with Bitmasking
Given the small constraint on `target.length` (k <= 4), this problem can be efficiently solved using dynamic programming with bitmasking. The state of the DP can represent the subsets of `target` that have been satisfied. We can build up the solution by iterating through each number in `nums` and deciding how it can contribute to satisfying the targets, updating our minimum costs at each step.
**Time:** O(N * 3^k + P), where N is `nums.length`, k is `target.length`, and P is pre-computation time. The pre-computation of LCMs takes `O(k * 2^k)`. The main DP loop iterates N times, and each update can be done in `O(3^k)`. The provided code snippet uses an `O(4^k)` update which is also acceptable for `k<=4`. The `O(3^k)` update is `for (mask) for (submask of mask) ...`. · **Space:** O(2^k), where k is `target.length`. This is for the DP table and the precomputed LCMs. Given k <= 4, this is very small.
**Pros:** Highly efficient and well-suited for the given constraints, especially the small size of `target`.; Guarantees finding the minimum possible cost by systematically exploring the solution space without redundant calculations.
**Cons:** More complex to conceptualize and implement compared to a simple recursive solution.; Requires understanding of bit manipulation, dynamic programming on subsets, and number theory concepts like LCM.
### Explanation
We define a DP array, `dp`, of size `2^k`, where `dp[mask]` stores the minimum total increments needed to satisfy the subset of `target` elements represented by the bitmask `mask`. We initialize `dp[0] = 0` and all other entries to infinity.

The core idea is to process each number from the `nums` array one by one and see how it can improve our current solution. For each `num` in `nums`, we can use it to satisfy any non-empty subset of targets (`submask`). The cost to do so is the number of increments to make `num` a common multiple of all targets in `submask`. This is equivalent to making `num` a multiple of their Least Common Multiple (LCM). The cost to change `num` to the smallest multiple of `L` (where `L = lcm(targets in submask)`) that is greater than or equal to `num` is `(L - (num % L)) % L`.

We iterate through each `num` and update the `dp` table. The update rule is `dp[mask] = min(dp[mask], dp[prev_mask] + cost_for_submask)`, where `mask = prev_mask | submask`. This can be implemented efficiently by iterating through all masks and their submasks, a classic `O(3^k)` pattern for subset DP. After considering all numbers in `nums`, `dp[(1<<k)-1]` will contain the minimum cost to satisfy all targets.

```java
import java.util.Arrays;

class Solution {
    public int minimumValueSum(int[] nums, int[] target) {
        int k = target.length;
        int numMasks = 1 << k;
        long[] dp = new long[numMasks];
        Arrays.fill(dp, Long.MAX_VALUE / 2);
        dp[0] = 0;

        long[] lcmOfMask = new long[numMasks];
        for (int mask = 1; mask < numMasks; mask++) {
            long currentLcm = 1;
            for (int i = 0; i < k; i++) {
                if ((mask & (1 << i)) != 0) {
                    currentLcm = lcm(currentLcm, target[i]);
                    // If LCM exceeds a reasonable bound, it's likely not part of an optimal solution.
                    // A safe upper bound could be max(nums) + max(target), but LCM can grow very large.
                    // For this problem, we assume it fits in long.
                }
            }
            lcmOfMask[mask] = currentLcm;
        }

        for (int num : nums) {
            long[] costForNum = new long[numMasks];
            for (int mask = 1; mask < numMasks; mask++) {
                long l = lcmOfMask[mask];
                if (l <= 0) { // Should not happen with positive targets
                    costForNum[mask] = Long.MAX_VALUE / 2;
                    continue;
                }
                long rem = num % l;
                costForNum[mask] = (rem == 0) ? 0 : (l - rem);
            }

            for (int mask = numMasks - 1; mask >= 0; mask--) {
                if (dp[mask] >= Long.MAX_VALUE / 2) continue;
                for (int submask = 1; submask < numMasks; submask++) {
                    if ((mask & submask) == 0) { // if submask covers new targets
                        int nextMask = mask | submask;
                        dp[nextMask] = Math.min(dp[nextMask], dp[mask] + costForNum[submask]);
                    }
                }
            }
        }

        long result = dp[numMasks - 1];
        return result >= Long.MAX_VALUE / 2 ? -1 : (int) result;
    }

    private long gcd(long a, long b) {
        while (b > 0) {
            long temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }

    private long lcm(long a, long b) {
        if (a == 0 || b == 0) return 0;
        // (a*b)/gcd to avoid overflow
        return (a / gcd(a, b)) * b;
    }
}
```
### Algorithm
- Let `k = target.length`. Initialize a DP array `dp` of size `2^k`. `dp[mask]` will store the minimum cost to satisfy the subset of `target` elements represented by `mask`.
- Initialize `dp[0] = 0` and all other `dp[mask]` to a very large value (infinity).
- Pre-calculate the least common multiple (LCM) for each of the `2^k - 1` non-empty subsets of `target`. Store these in an array, say `lcmOfMask`. Be sure to use `long` to prevent overflow.
- Iterate through each `num` in the `nums` array:
  - For the current `num`, calculate the cost to make it a multiple of the LCM for each `submask`. The cost for a `submask` with LCM `L` is `(L - (num % L)) % L`. Store these costs in a temporary array `costForNum`.
  - Update the `dp` array. Iterate `mask` from `(1 << k) - 1` down to `0`. For each `mask`, iterate through all its submasks `submask`.
  - The new cost for `mask` is updated as: `dp[mask] = min(dp[mask], dp[mask ^ submask] + costForNum[submask])`.
  - The downward iteration of `mask` is crucial for the space-optimized in-place update, as it ensures that when we calculate `dp[mask]`, `dp[mask ^ submask]` holds the value from before processing the current `num`.
- After iterating through all numbers in `nums`, the final answer is `dp[(1 << k) - 1]`, which is the minimum cost to satisfy all targets.