Short Problem Definition:
Given N integers, count the number of pairs of integers whose difference is K.
Link
Complexity:
time complexity is O(N*log(N))
space complexity is O(N)
Execution:
The solution is pretty straight-forward, just read the code :). The runtime complexity is calculated with log(N) access times for tree-based sets (not the case in Python).
Solution:
1
2
3
4
5
6
7
8
9
10
11
12
13
|
#!/usr/bin/py def pairs(a,k): answer = 0 s = set (a) for v in s: if v + k in s: answer + = 1 return answer if __name__ = = '__main__' : n, k = map ( int , raw_input ().split()) b = map ( int , raw_input ().split()) print pairs(b, k) |