###
__Problem__

https://www.interviewstreet.com/challenges/dashboard/#problem/4e14b83d5fd12__Problem__

Given N numbers , [N<=10^5] we need to count the total pairs of numbers that have a difference of K. [K>0 and K<1e9 span="span">

**Input Format:**

1st line contains N & K (integers).

2nd line contains N numbers of the set. All the N numbers are assured to be distinct.

**Output Format:**

One integer saying the no of pairs of numbers that have a diff K.

**Sample Input #00:**

5 2

1 5 3 4 2

**Sample Output #00:**3

**Analysis**

All Java Solutions on the InterviewStreet needs to run in 5 seconds with 256 MB maximum RAM available. So that means our solution can never be "Brute-Force" or O(n^2). Same applies to the space complexity.

The array contains 1,00,000 numbers and we need to find the pairs of numbers whose difference is K. There is a clue here that if the numbers are not sorted, we are only left with Brute-Force approach .

That means we need to check each number with every other number to see if they make a pair. This proves costly and we would run out of 5 seconds.

So one of the simplest solution is to sort the array using any inbuilt sort method. Now apply a modified version of binary search. So take each number 'x' and do a binary search for (x+k). If its found they make a pair. Now take the next number in the sorted array and so on.

**Solution**

## No comments:

## Post a Comment