Here is an interesting programming puzzle I came across . Given an array of positive integers, and a number K. We need to find pairs(a,b) from the array such that a % b = K
.
I have a naive O(n^2) solution to this where we can check for all pairs such that a%b=k. Works but inefficient. We can certainly do better than this can't we ? Any efficient algorithms for the same? Oh and it's NOT homework.
In order to find all the possible pairs from the array, we need to traverse the array and select the first element of the pair. Then we need to pair this element with all the elements in the array from index 0 to N-1. Below is the step by step approach: Traverse the array and select an element in each traversal.
Sort your array and binary search or keep a hash table with the count of each value in your array.
For a number x
, we can find the largest y
such that x mod y = K
as y = x - K
. Binary search for this y
or look it up in your hash and increment your count accordingly.
Now, this isn't necessarily the only value that will work. For example, 8 mod 6 = 8 mod 3 = 2
. We have:
x mod y = K => x = q*y + K =>
=> x = q(x - K) + K =>
=> x = 1(x - K) + K =>
=> x = 2(x - K)/2 + K =>
=> ...
This means you will have to test all divisors of y
as well. You can find the divisors in O(sqrt y)
, giving you a total complexity of O(n log n sqrt(max_value))
if using binary search and O(n sqrt(max_value))
with a hash table (recommended especially if your numbers aren't very large).
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With