Given N numbers , [N<=10^5] we need to count the total pairs of numbers that have a difference of K
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
Solution
This problem can be solved with hashing or by sorting.I have taken the sorting approach.
Sort the contents of the array in (n log n) time. Then for each number in the array, do a binary search to see if the num+k exists in the array.
In hashing approach, maintain a hashtable. As you iterate each number X, check if X+k exists in the hashtable with 1 value. If its there then you have a pair. Else put the key (X+k) and value '0'.
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
Solution
This problem can be solved with hashing or by sorting.I have taken the sorting approach.
Sort the contents of the array in (n log n) time. Then for each number in the array, do a binary search to see if the num+k exists in the array.
In hashing approach, maintain a hashtable. As you iterate each number X, check if X+k exists in the hashtable with 1 value. If its there then you have a pair. Else put the key (X+k) and value '0'.
No comments:
Post a Comment