Problem

You are given a 0-indexed array nums consisting of positive integers, representing targets on a number line. You are also given an integer space.

You have a machine which can destroy targets. Seeding the machine with some nums[i] allows it to destroy all targets with values that can be represented as nums[i] + c * space, where c is any non-negative integer. You want to destroy the maximum number of targets in nums.

Return _theminimum value of _nums[i]you can seed the machine with to destroy the maximum number of targets.

Examples

Example 1

1
2
3
4
5

Input: nums = [3,7,8,1,1,5], space = 2
Output: 1
Explanation: If we seed the machine with nums[3], then we destroy all targets equal to 1,3,5,7,9,... 
In this case, we would destroy 5 total targets (all except for nums[2]). 
It is impossible to destroy more than 5 targets, so we return nums[3].

Example 2

1
2
3
4
5

Input: nums = [1,3,5,2,4,6], space = 2
Output: 1
Explanation: Seeding the machine with nums[0], or nums[3] destroys 3 targets. 
It is not possible to destroy more than 3 targets.
Since nums[0] is the minimal integer that can destroy 3 targets, we return 1.

Example 3

1
2
3

Input: nums = [6,2,5], space = 100
Output: 2
Explanation: Whatever initial seed we select, we can only destroy 1 target. The minimal seed is nums[1].

Constraints

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^9
  • 1 <= space <= 10^9

Solution

Method 1 – Hashing Remainders (Greedy)

Intuition

Targets that can be destroyed by the same seed must have the same remainder when divided by space. So, group numbers by their remainder modulo space and pick the group with the most elements. Among all possible seeds in that group, choose the smallest number.

Approach

  1. For each number in nums, compute num % space and count the frequency of each remainder.
  2. Track the maximum frequency and the smallest number for each remainder.
  3. After processing, select the remainder with the highest frequency. If there are ties, pick the group with the smallest seed.
  4. Return the smallest seed from the group with the highest frequency.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
    int destroyTargets(vector<int>& nums, int space) {
        unordered_map<int, int> cnt;
        unordered_map<int, int> mn;
        for (int x : nums) {
            int r = x % space;
            cnt[r]++;
            if (!mn.count(r) || x < mn[r]) mn[r] = x;
        }
        int mx = 0, ans = INT_MAX;
        for (auto& [r, c] : cnt) {
            if (c > mx || (c == mx && mn[r] < ans)) {
                mx = c;
                ans = mn[r];
            }
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

func destroyTargets(nums []int, space int) int {
    cnt := map[int]int{}
    mn := map[int]int{}
    for _, x := range nums {
        r := x % space
        cnt[r]++
        if v, ok := mn[r]; !ok || x < v {
            mn[r] = x
        }
    }
    mx, ans := 0, 1<<31-1
    for r, c := range cnt {
        if c > mx || (c == mx && mn[r] < ans) {
            mx = c
            ans = mn[r]
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    public int destroyTargets(int[] nums, int space) {
        Map<Integer, Integer> cnt = new HashMap<>();
        Map<Integer, Integer> mn = new HashMap<>();
        for (int x : nums) {
            int r = x % space;
            cnt.put(r, cnt.getOrDefault(r, 0) + 1);
            mn.put(r, Math.min(mn.getOrDefault(r, x), x));
        }
        int mx = 0, ans = Integer.MAX_VALUE;
        for (int r : cnt.keySet()) {
            int c = cnt.get(r);
            if (c > mx || (c == mx && mn.get(r) < ans)) {
                mx = c;
                ans = mn.get(r);
            }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    fun destroyTargets(nums: IntArray, space: Int): Int {
        val cnt = mutableMapOf<Int, Int>()
        val mn = mutableMapOf<Int, Int>()
        for (x in nums) {
            val r = x % space
            cnt[r] = cnt.getOrDefault(r, 0) + 1
            mn[r] = minOf(mn.getOrDefault(r, x), x)
        }
        var mx = 0
        var ans = Int.MAX_VALUE
        for (r in cnt.keys) {
            val c = cnt[r]!!
            if (c > mx || (c == mx && mn[r]!! < ans)) {
                mx = c
                ans = mn[r]!!
            }
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution:
    def destroyTargets(self, nums: list[int], space: int) -> int:
        cnt: dict[int, int] = {}
        mn: dict[int, int] = {}
        for x in nums:
            r = x % space
            cnt[r] = cnt.get(r, 0) + 1
            mn[r] = min(mn.get(r, x), x)
        mx = 0
        ans = float('inf')
        for r in cnt:
            c = cnt[r]
            if c > mx or (c == mx and mn[r] < ans):
                mx = c
                ans = mn[r]
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

impl Solution {
    pub fn destroy_targets(nums: Vec<i32>, space: i32) -> i32 {
        use std::collections::HashMap;
        let mut cnt = HashMap::new();
        let mut mn = HashMap::new();
        for &x in &nums {
            let r = x % space;
            *cnt.entry(r).or_insert(0) += 1;
            mn.entry(r).and_modify(|v| *v = (*v).min(x)).or_insert(x);
        }
        let mut mx = 0;
        let mut ans = i32::MAX;
        for (&r, &c) in &cnt {
            let m = mn[&r];
            if c > mx || (c == mx && m < ans) {
                mx = c;
                ans = m;
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    destroyTargets(nums: number[], space: number): number {
        const cnt = new Map<number, number>();
        const mn = new Map<number, number>();
        for (const x of nums) {
            const r = x % space;
            cnt.set(r, (cnt.get(r) ?? 0) + 1);
            mn.set(r, Math.min(mn.get(r) ?? x, x));
        }
        let mx = 0, ans = Number.MAX_SAFE_INTEGER;
        for (const [r, c] of cnt.entries()) {
            const m = mn.get(r)!;
            if (c > mx || (c === mx && m < ans)) {
                mx = c;
                ans = m;
            }
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of nums. We process each number once.
  • 🧺 Space complexity: O(n), for storing the counts and minimums for each remainder.