| Submit | All submissions | Best solutions | Back to list |
HACKRNDM - Hacking the random number generator |
You recently wrote a random number generator code for a web application and now you notice that some cracker has cracked it. It now gives numbers at a difference of some given value k more predominantly. You being a hacker decide to write a code that will take in n numbers as input and a value k and find the total number of pairs of numbers whose absolute difference is equal to k, in order to assist you in your random number generator testing.
NOTE: All values fit in the range of a signed integer, n, k>=1
Input
1st line contains n & k.
2nd line contains n numbers of the set. All the n numbers are assured to be distinct.
(Edited: n <= 10^5)
Output
One integer saying the no of pairs of numbers that have a diff k.
Example
Input: 5 2
1 5 3 4 2 Output: 3
| Added by: | vijay |
| Date: | 2011-10-15 |
| Time limit: | 1s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All except: ASM64 |
| Resource: | Own Problem |
hide comments
|
||||||||||||||
|
2017-06-11 15:17:36
0.09 secs using unordered_maps 0.07 secs using Binary Search |
||||||||||||||
|
2017-05-27 13:59:35 wisfaq
Python users be careful: the n elements of the set are all on a separate line! |
||||||||||||||
|
2017-03-31 00:51:39
AC in one go///// simple sort and two pointer game/// |
||||||||||||||
|
2017-03-15 09:58:45
simple use of binary search |
||||||||||||||
|
2017-03-09 08:27:36
AC in one GO! Sort + binary search works like charm! |
||||||||||||||
|
2017-02-12 14:01:27
Easy..!! AC in one Go!! using java.util.HashMap; |
||||||||||||||
|
2016-12-11 20:07:13 aeon
if you are using unordered_map and c++ as your submission language use c++14(g++5.1), other versions cost me 1 compilation Error. |
||||||||||||||
|
2016-12-10 05:36:45
map-O(nlogn+n)-0.13 unordered_map-O(n)-0.05 binarysearch-O(nlogn+nlogn)-0.04 (but why did nlogn solution took less time than O(n)...i don't get it) |
||||||||||||||
|
2016-10-25 18:34:13
AC in C++ -- binary Search 0.04 sec O(N * log(N) + N*log(N) ) -- two pointers with sort 0.03 sec O(N * log(N) + N) Last edit: 2016-10-25 18:35:40 |
||||||||||||||
|
2016-10-25 14:29:26
Very easy with maps, will try the trivial binary search approach too. :) |
||||||||||||||
RSS