Minimum Increments for Target Multiples in an 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.

Examples

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 * 10^4
• 1 <= target.length <= 4
• target.length <= nums.length
• 1 <= nums[i], target[i] <= 10^4

Solution

Method 1 – Greedy Increment with Divisor Mapping

Intuition

For each target value, we need at least one number in nums that is a multiple of it. For each target, find the closest multiple in nums (possibly after increments) and sum the required increments. We can use a mapping from each target to the minimum increment needed.

Approach

1. For each target value, check all nums and compute the minimum increment needed to make some nums[j] a multiple of target[i].
2. For each nums[j], if nums[j] >= target[i], compute the remainder and the increment needed to reach the next multiple.
3. Track the minimum increment for each target.
4. Sum the minimum increments for all targets.

Code

C++

class Solution {
public:
    int minOperations(vector<int>& nums, vector<int>& target) {
        int ans = 0;
        for (int t : target) {
            int mn = INT_MAX;
            for (int x : nums) {
                int need = (x >= t) ? (x % t == 0 ? 0 : t - x % t) : t - x;
                mn = min(mn, need);
            }
            ans += mn;
        }
        return ans;
    }
};

Go

func minOperations(nums []int, target []int) int {
    ans := 0
    for _, t := range target {
        mn := 1 << 30
        for _, x := range nums {
            var need int
            if x >= t {
                if x%t == 0 {
                    need = 0
                } else {
                    need = t - x%t
                }
            } else {
                need = t - x
            }
            if need < mn {
                mn = need
            }
        }
        ans += mn
    }
    return ans
}

Java

class Solution {
    public int minOperations(int[] nums, int[] target) {
        int ans = 0;
        for (int t : target) {
            int mn = Integer.MAX_VALUE;
            for (int x : nums) {
                int need = x >= t ? (x % t == 0 ? 0 : t - x % t) : t - x;
                mn = Math.min(mn, need);
            }
            ans += mn;
        }
        return ans;
    }
}

Kotlin

class Solution {
    fun minOperations(nums: IntArray, target: IntArray): Int {
        var ans = 0
        for (t in target) {
            var mn = Int.MAX_VALUE
            for (x in nums) {
                val need = if (x >= t) if (x % t == 0) 0 else t - x % t else t - x
                mn = minOf(mn, need)
            }
            ans += mn
        }
        return ans
    }
}

Python

def min_operations(nums: list[int], target: list[int]) -> int:
    ans = 0
    for t in target:
        mn = float('inf')
        for x in nums:
            need = (x >= t) and (x % t == 0) and 0 or (x >= t) and (t - x % t) or (t - x)
            mn = min(mn, need)
        ans += mn
    return ans

Rust

impl Solution {
    pub fn min_operations(nums: Vec<i32>, target: Vec<i32>) -> i32 {
        let mut ans = 0;
        for &t in &target {
            let mut mn = i32::MAX;
            for &x in &nums {
                let need = if x >= t {
                    if x % t == 0 { 0 } else { t - x % t }
                } else {
                    t - x
                };
                mn = mn.min(need);
            }
            ans += mn;
        }
        ans
    }
}

TypeScript

class Solution {
    minOperations(nums: number[], target: number[]): number {
        let ans = 0;
        for (let t of target) {
            let mn = Number.MAX_SAFE_INTEGER;
            for (let x of nums) {
                let need = x >= t ? (x % t === 0 ? 0 : t - x % t) : t - x;
                mn = Math.min(mn, need);
            }
            ans += mn;
        }
        return ans;
    }
}

Complexity

• ⏰ Time complexity: O(n * m), where n is the length of nums and m is the length of target. Each target is checked against all nums.
• 🧺 Space complexity: O(1), only a few variables are used for tracking the answer.