Destroy Sequential Targets - Practice Coding Problems

Destroy Sequential Targets - 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 the minimum value of nums[i] you can seed the machine with to destroy the maximum number of targets.

Input & Output

Example 1 — Basic Case

$ Input: nums = [3,6,2,4,1], space = 2

› Output: 2

💡 Note: Seeding with 2 destroys targets [2,4,6] (3 targets). Seeding with 1 destroys [1,3] (2 targets). Choose 2 for maximum targets.

Example 2 — Tie Breaker

$ Input: nums = [1,3,5,2,4,6], space = 2

› Output: 1

💡 Note: Both remainder groups have 3 targets: [1,3,5] and [2,4,6]. Choose seed=1 (minimum value) from the first group.

Example 3 — Single Group

$ Input: nums = [6,2,5], space = 100

› Output: 2

💡 Note: Since space=100 is larger than differences, each target forms its own group. Choose minimum value 2.

Constraints

1 ≤ nums.length ≤ 10⁵
1 ≤ nums[i], space ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input

Array of targets and space interval

Process

Group targets that can be destroyed by same seed

Output

Minimum seed value that destroys maximum targets

Key Takeaway

🎯 Key Insight: Targets that differ by multiples of 'space' can be destroyed by the same seed

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is that targets with the same remainder when divided by space can be destroyed by the same seed. Use modular arithmetic to group targets efficiently. Best approach is hash map grouping. Time: O(n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Modular Arithmetic with Hash Map	O(n)	O(n)	Group targets by their remainder when divided by space, find the group with most elements
Brute Force	O(n²)	O(1)	Try each number as seed and count how many targets it can destroy

Modular Arithmetic with Hash Map — Algorithm Steps

Calculate remainder = nums[i] % space for each target
Group targets by their remainder using a hash map
For each group, track count and minimum value
Return minimum value from the group with maximum count

Visualization

Tap to expand

Step-by-Step Walkthrough

Calculate Remainders

Find nums[i] % space for each target

Group by Remainder

Targets with same remainder can be destroyed together

Find Best Group

Choose group with most targets (minimum seed if tied)

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

#define MAX_NUMS 100000

typedef struct {
    int remainder;
    int count;
    int minValue;
} RemainderInfo;

int solution(int* nums, int numsSize, int space) {
    RemainderInfo remainders[MAX_NUMS];
    int remainderCount = 0;
    
    // Group targets by remainder
    for (int i = 0; i < numsSize; i++) {
        int remainder = nums[i] % space;
        int found = -1;
        
        // Find existing remainder group
        for (int j = 0; j < remainderCount; j++) {
            if (remainders[j].remainder == remainder) {
                found = j;
                break;
            }
        }
        
        if (found != -1) {
            remainders[found].count++;
            if (nums[i] < remainders[found].minValue) {
                remainders[found].minValue = nums[i];
            }
        } else {
            remainders[remainderCount].remainder = remainder;
            remainders[remainderCount].count = 1;
            remainders[remainderCount].minValue = nums[i];
            remainderCount++;
        }
    }
    
    int maxCount = 0;
    int result = INT_MAX;
    
    // Find best remainder group
    for (int i = 0; i < remainderCount; i++) {
        if (remainders[i].count > maxCount || 
            (remainders[i].count == maxCount && remainders[i].minValue < result)) {
            maxCount = remainders[i].count;
            result = remainders[i].minValue;
        }
    }
    
    return result;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    line[strcspn(line, "\n")] = 0;
    
    int nums[1000];
    int numsSize = 0;
    char* ptr = line + 1;
    char* token;
    while ((token = strtok(ptr, ",]")) != NULL) {
        nums[numsSize++] = atoi(token);
        ptr = NULL;
    }
    
    int space;
    scanf("%d", &space);
    
    printf("%d\n", solution(nums, numsSize, space));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through array to build frequency map and find result

✓ Linear Growth

Space Complexity

O(n)

Hash map stores up to n entries in worst case (all different remainders)

⚡ Linearithmic Space

12.5K Views

Medium Frequency

~15 min Avg. Time

456 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Modular Arithmetic with Hash Map — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler