patternrubyMinor
Counting all pairs that differ by k
Viewed 0 times
countingallthatdifferpairs
Problem
Given an array of numbers and another number k, how can I find the number of 2 elements such as their difference is equal to k?
I ran a test where n was an array of 8000 different 10 digit numbers.
However, this took about 30 seconds to solve, and ideally it would solve in under a second.
It looks like there is a problem with my algorithm, but I can't figure out how to make it more efficient.
def pairs(n,k)
n.combination(2).select{|x|(x[0]-x[1] == k) || (x[1]-x[0] == k)}.count
endI ran a test where n was an array of 8000 different 10 digit numbers.
However, this took about 30 seconds to solve, and ideally it would solve in under a second.
It looks like there is a problem with my algorithm, but I can't figure out how to make it more efficient.
Solution
The logical solution here is to sort the data in order, then scan it looking ahead for the partner that has the right difference to the target. Slicing, and combinations, etc. are not going to be the most efficient algorithm.
A sort with \$O(n \log n)\$ scaling, and a simple 'look ahead' to find a potential pairing, will be much, much faster.
If your data has duplicates, then you will need to look for multiple matches for the correct difference.
Consider doing a binary search for the target value, which will still leave you at an overall performance of \$O(n \log n)\$ algorithm
A sort with \$O(n \log n)\$ scaling, and a simple 'look ahead' to find a potential pairing, will be much, much faster.
If your data has duplicates, then you will need to look for multiple matches for the correct difference.
Consider doing a binary search for the target value, which will still leave you at an overall performance of \$O(n \log n)\$ algorithm
Context
StackExchange Code Review Q#69105, answer score: 8
Revisions (0)
No revisions yet.