Welcome to Subscribe On Youtube

2453. Destroy Sequential Targets

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 <= 105
  • 1 <= nums[i] <= 109
  • 1 <= 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 {
        public int destroyTargets(int[] nums, int space) {
            Map<Integer, Integer> cnt = new HashMap<>();
            for (int v : nums) {
                v %= space;
                cnt.put(v, cnt.getOrDefault(v, 0) + 1);
            }
            int ans = 0, mx = 0;
            for (int v : nums) {
                int t = cnt.get(v % space);
                if (t > mx || (t == mx && v < ans)) {
                    ans = v;
                    mx = t;
                }
            }
            return ans;
        }
    }
    
  • class Solution {
    public:
        int destroyTargets(vector<int>& nums, int space) {
            unordered_map<int, int> cnt;
            for (int v : nums) ++cnt[v % space];
            int ans = 0, mx = 0;
            for (int v : nums) {
                int t = cnt[v % space];
                if (t > mx || (t == mx && v < ans)) {
                    ans = v;
                    mx = t;
                }
            }
            return ans;
        }
    };
    
  • 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
    
    
  • func destroyTargets(nums []int, space int) int {
    	cnt := map[int]int{}
    	for _, v := range nums {
    		cnt[v%space]++
    	}
    	ans, mx := 0, 0
    	for _, v := range nums {
    		t := cnt[v%space]
    		if t > mx || (t == mx && v < ans) {
    			ans = v
    			mx = t
    		}
    	}
    	return ans
    }
    

All Problems

All Solutions