5 ms·

Consider me sniped. My first thought was hashing mod k. Then when you create your hashmap you just check for collisions as you go and then test that they're k a

Consider me sniped. My first thought was hashing mod k. Then when you create your hashmap you just check for collisions as you go and then test that they're k apart as opposed to 2k,3k etc. Then you don't have to scan through the hashmap again. It seems like if the parameters described in the problem are uniformly distributed, ie k is generally pretty big and you don't have a huge list of numbers then this initial filter would get you really close.

ohyes 9y ago
I had this thought too. If you check N+K and N-K you only need to scan the numbers once. The theoretically fastest implementation would probably use a bitmap, you'd only need 125 megabytes. (you'd dereference the offset and check the appropriate bit with a mask). It would be interesting to see if this is faster or slower. I'm going to go try it out.
- dithering 9y ago
  Surely you only need to check N+K? Because if (N1,N2) satisfies N+K, then (N2,N1) must satisfy N-K? You can also stop when you hit Nmax-K... might save a few lookups when K is large.
  - ohyes 9y ago
    If you're computing the hash-table ahead of time you only need to do n+k. If you're setting the value in the hash table as you check it (as you would in a single pass), you have to do n-k as well. This is because the number you are currently adding didn't exist in the array when you checked n+k for the previous numbers.
- jfoutz 9y ago
  You might get some milage out of partitioning on k, make k hashtables, for n, hash n/k into the n%k table. then just look for adjacency. doesn't improve the worst case at all, k=1, or all n's fall in the same bucket, but in the average (maybe? no idea about the actual data) case it would help with collisions, or reducing the size of the sorted arrays. Also, it becomes embarrassingly parallel. A trivial next step is one thread per hashtable. Of course, all that overhead might be a big waste of time.
nandemo 9y ago
I might be wrong but that looks like O(n^2) in the worst case, namely when the input is some permutation of (a+k, a+2k,...,a+nk).

ohyes 9y ago

I had this thought too. If you check N+K and N-K you only need to scan the numbers once. The theoretically fastest implementation would probably use a bitmap, you'd only need 125 megabytes. (you'd dereference the offset and check the appropriate bit with a mask). It would be interesting to see if this is faster or slower. I'm going to go try it out.

dithering 9y ago
Surely you only need to check N+K? Because if (N1,N2) satisfies N+K, then (N2,N1) must satisfy N-K? You can also stop when you hit Nmax-K... might save a few lookups when K is large.
- ohyes 9y ago
  If you're computing the hash-table ahead of time you only need to do n+k. If you're setting the value in the hash table as you check it (as you would in a single pass), you have to do n-k as well. This is because the number you are currently adding didn't exist in the array when you checked n+k for the previous numbers.
jfoutz 9y ago
You might get some milage out of partitioning on k, make k hashtables, for n, hash n/k into the n%k table. then just look for adjacency. doesn't improve the worst case at all, k=1, or all n's fall in the same bucket, but in the average (maybe? no idea about the actual data) case it would help with collisions, or reducing the size of the sorted arrays. Also, it becomes embarrassingly parallel. A trivial next step is one thread per hashtable. Of course, all that overhead might be a big waste of time.

nandemo 9y ago

I might be wrong but that looks like O(n^2) in the worst case, namely when the input is some permutation of (a+k, a+2k,...,a+nk).