Faster algorithm than nested loops?
For the google codeJam qualification round one of the problems was finding how many 'recycled pairs' there are between two given integers.
This was my solution but it wasn't fast enough for the large data input set. Given something like @a = 10, @b = 200000 it starts to get slow.
I think my solution would be O(2^n) (I don't have a solid grasp on big O analysis yet) which is horrible. I was wondering if theres a standard way to iterate through two loops like this with a faster algorithm?
def getPairs (@a..@b).each do |n| (n..@b).each do |m| if (containsSame(n,m)) && (isMatch(@a, n, m, @b)) @recycledPairs += 1 end end end end
edit: From Google CodeJam site:
Let's say a pair of distinct positive integers (n, m) is recycled if you can obtain m by moving some digits from the back of n to the front without changing their order. For example, (12345, 34512) is a recycled pair since you can obtain 34512 by moving 345 from the end of 12345 to the front. Note that n and m must have the same number of digits in order to be a recycled pair. Neither n nor m can have leading zeros.
You can read the official analysis of this problem for the correct solution.
Basically, the solution is to compute all the distinct rotations larger than n, but not larger than B for each n.
The description says "Note that n and m must have the same number of digits in order to be a recycled pair."
Your inner loop takes not take account of that. If @a = 2 and @b = 20,000 then you can cut out whole chunks of the inner loop. If n is two digits, then you only need to test two digit values of m. Look carefully at the upper limit of your inner loop.
From the statement: max b is at most 2*10^6. As with all codejam problems you have multitests.
Step 1: Precalc. For each number n = [1..maxb], save all cycled from it numbers that are strictly less then it(no more than 7 for each) e.g
10 - 1 321 - 132, 213
Step 2: for each test. Walk through each number from A to B, and count the numbers of "cycled" that are between A and B.
Time complexity: Step 1 works in (number of digits) for each number, i.e. O(ln n). You have to do it b times. All in all O(b*ln b). Same goes for step 2. This works less than a second on big test case.