Destroy Sequential Targets
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 = 2Output
1If seeded with 1, the machine destroys targets equal to 1, 3, 5, 7, 9, ... for 5 total targets, which is maximal.
Example 2
Input
nums = [1,3,5,2,4,6], space = 2Output
1Seeding with 1 or 2 destroys 3 targets, and 1 is the minimum seed value that achieves this maximum.
Constraints
- 1 <= nums.length <= 10^5
- 1 <= nums[i] <= 10^9
- 1 <= space <= 10^9
Asked at 1 companies
Practice questions like this out loud in a mock coding interview with a live AI interviewer. First one free.