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

  • 1N106
  • 1K,nums[i]106
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

?