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

1
2
3
4
5

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

1
2
3
4
5

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

1
2
3
4
5

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

Examples

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

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;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

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
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

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;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

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
    }
}
1
2
3
4
5
6
7
8
9

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
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

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
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

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.