Cisco OA-6 2022

Problem Description

A grocery store needs to select a set of apples where the weight difference between the largest and smallest apple is no more than k. Given the range k, find the maximum number of apples that can be selected from the input set of N apples.

Input Format:

1. The first line contains the range K.
2. The second line contains the number of apples N.
3. Subsequent lines contain the size of each apple (one per line).

Constraints:

• The range K can vary from 0 to 10,000.
• The number of apples (N) can vary from 1 to 10,000.
• The size of each apple can vary from 1 to 10,000.

Output:

Return an integer specifying the maximum number of apples that can be selected within the weight difference range of K.

Test Case Example 1

Input:

2
8
4
2
6
100
101
101
110
102

Output:

4

Explanation:

The input specifies a maximum allowable weight difference of 2. There are 8 apples provided as input, along with their respective weights.

From this input, 3 different subsets can be formed, where each subset contains apples with weight differences of 2 or less between any two apples:

• Subset 1: {2, 4}
• Subset 2: {4, 6}
• Subset 3: {100, 101, 101, 102}

Among these, the largest subset is the one with 4 apples: {100, 101, 101, 102}.

Thus, the maximum number of apples in any subset is 4.