Description
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 the minimum value of nums[i] you can seed the machine with to destroy the maximum number of targets.
Example 1:
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:
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:
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 <= 1051 <= nums[i] <= 1091 <= space <= 109
Solutions
Solution 1: Modulo + Enumeration
We traverse the array nums and use a hash table cnt to count the frequency of each number modulo space. The higher the frequency, the more targets can be destroyed. We find the group with the highest frequency and take the minimum value in the group.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the array nums.
class Solution: def destroyTargets(self, nums: List[int], space: int) -> int: cnt = Counter(v % space for v in nums) ans = mx = 0 for v in nums: t = cnt[v % space] if t > mx or (t == mx and v < ans): ans = v mx = t return ans(code-box)
