Maximum Operation Count

2.7

3 votes
Greedy algorithm, Greedy Algorithms, Algorithms, Basics of Greedy Algorithms, Datastructures
Problem

We have given an array \(nums\) of integers of size \(N\) and a positive integer \(K\). We can perform as many operations on the array till it has at least two elements. 
The operation is as follows: you can pick any two numbers from the array and remove both if the difference between them is at least \(K\).
Find the maximum number of times we can perform this operation on the array.

Input format

  • The first line contains two space-separated integers \(N\) and \(K\).
  • The second line contains \(N\) space-separated integers denoting array \(nums\).

Output format

  • Print the maximum possible number of operations.

Constraints

  • \(1 \leq N \leq 10^6 \)
  • \( 1 \leq K, nums[i] \leq 10^6 \)
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

One of the possibility for performing maximum number of operation on given array.
After 1st operation \(nums\) = [1,2,3,5].
After 2nd operation \(nums\) = [2,3].

Editor Image

?