Minimum Increments for Target Multiples in an Array - Solution & Explanation

Problem Overview: You are given an array of numbers and a set of target values. You may increment any element any number of times. The goal is to ensure that for every target value, at least one array element becomes a multiple of it while minimizing the total increments performed.

Approach 1: Brute Force Assignment (Exponential Time, High Space)

The direct idea is to try assigning each array element to cover different target values. For every target, compute the cost to increment a number until it becomes a multiple of that target using (t - num % t) % t. Then explore all assignments of numbers to targets. This quickly becomes exponential because each element could serve multiple targets and every combination must be evaluated. Time complexity grows roughly O(n^m) with O(m) auxiliary space, making it impractical when the number of targets increases.

Approach 2: LCM + Bitmask Dynamic Programming (O(n · 2^m · m), Space O(2^m))

The key observation: a single number can satisfy multiple targets if it becomes a multiple of the LCM of those targets. Precompute the lcm for every subset of targets using bitmask representation. For each number in the array, calculate the cost to raise it to the next multiple of each subset LCM using (L - num % L) % L. Then run dynamic programming where dp[mask] represents the minimum cost to satisfy the targets represented by that mask.

Iterate through each array value and attempt to extend previously covered target sets. For every current mask and subset mask, update dp[newMask] where newMask = mask | subset. This works because making a number divisible by the LCM automatically makes it divisible by every target inside that subset. Precomputing subset LCMs keeps transitions fast and avoids repeated number theory calculations.

This transforms the problem into covering all targets (mask = (1<<m)-1) with minimal cost. The bitmask ensures each combination of satisfied targets is tracked efficiently. Since the number of targets is small, 2^m states remain manageable.

Recommended for interviews: The LCM + bitmask DP approach. Interviewers expect recognition that multiple targets can be satisfied simultaneously via LCM, followed by a DP over subsets. Mentioning the brute force shows understanding of the search space, but the bitmask optimization demonstrates strong algorithmic thinking.