SPOJ: HACKRNDM

Here we are given 2 integers, n and k. Then follows n lines each with an integer. We have to print the number of pairs whose absolute difference is equal to k.

The question is similar to the question k-difference at Interviewstreet. The noob solution is to hold each element and compute difference with all other elements and if it equals to k, increase count by 1. O(n^2)

But the best way is to add all elements in a set, create another set with all the numbers and k added to each of them. Thus, if A = [1, 5, 3, 4, 2] and k=2, then newset = [3, 7, 5, 6, 4]. Now finding the length of the intersection of the two sets would give the answer.

My solution was in python.

I did this which ran at 1.99:

 
len(nums & newset)   

Then I did this which gave 1.78:

 
len(nums.intersection(newset))

This proves the second one is faster.