Challenges

Rotate Array
You are given an array of N length. You have to rotate the array right...
Max. Marks: 6
Solved By : 983
Floating Number
Bob has a floating point number N. He wants to set the precision for 2...
Max. Marks: 4
Solved By : 4573
SwapMaster solves Symmetric Swap
The SwapMaster is known to be the greatest and fastest swapper of all ...
Max. Marks: 4
Solved By : 3957
String Matching
Cody has a sequence of characters N. He likes a sequence if it contain...
Max. Marks: 3
Solved By : 2125
Leap Year
Steve is playing a quiz game with his brother John. As Steve just lear...
Max. Marks: 6
Solved By : 3313
Project Teams
There are N students in a class and Teacher want to divide these stude...
Max. Marks: 5
Solved By : 4078
Circle of Numbers
All numbers in NumberLand are standing in a circle for a dancing cerem...
Max. Marks: 6
Solved By : 2815
Happy String
A happy string is a string in which each character is lexicographicall...
Max. Marks: 4
Solved By : 2099
Degree Celsius
Tom is a scientist. He uses huge machines for complex calculations. Th...
Max. Marks: 4
Solved By : 4761
Three's Company
This problem requires you to create a output string from input string ...
Max. Marks: 4
Solved By : 3135
Depleting Ammunition
Please select a challenge
Problem Statement
A war has started between two rival countries A and B. Country A wants to destroy the Capital city of B through aerial bombing. But due to the sudden outbreak of war, the ammunition reserves are low on both sides. Due to less quantity of ammunation, fighter pilot Jeff has been asked to carry the exact number of bombs that are required to destroy the whole city. Each bomb can be dropped on a building only. Capital of country B is a one dimensional city with n buildings, where each building (i) is located at some x(i) on the x-axis. Jeff has to destroy every building in the city. Each bomb has a destructive range k, meaning it can destroy everything at a distance ≤ k units away from its point of impact. Now given a map of the city and the range k of the bomb, Jeff wants you to find the minimum number of bombs he needs to destroy the whole city(each building must be in the destructive range of atleast one bomb).

Input
The first line contains two space-separated integers n(number of buildings in the city) and k(range of destruction of each bomb). The second line contains n space-separated integers, depicting the location of buildings on the x-axis.

Output
Print a single integer denoting the minimum number of bombs required to destroy the city.

Constraints
1 ≤ n,k ≤ 10^5 1 ≤ x ≤ 10^5

Sample Input
4 2
1 2 3 4

Sample Output

1

Dcoded By: Rajat Gupta

Solved By: 237

Maximum Marks: 15