We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
My Stern-Brocot approach takes 0.054 seconds for that sample. Let the "SB enumeration" of a/b be a sequence of Ls and Rs depecting the left and right branches taken in the tree. Then 1/n is a sequence of n-1 Ls. I'm guessing that in your approach, you took one L (or R) at a time. But it's possible to calculate how many Ls (or Rs) to take in a row at each change in direction, thus going from 1/1 to 1/n in a single iteration, instead of n-1 iterations.
Once you find a/b in the Stern-Borcot tree, there are only two possible paths to find the answer (due to the sorted nature of the tree), which can both be found in constant time. The worst case for finding a/b is LRLRLRLR... which corresponds to the Fibonacci numbers; Fib(n) is approximately phi^n, so the algorithm to find a/b is O(log(b)).
I don't want to reveal to much here, but message me if you're still interested in the algorithm.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Project Euler #71: Ordered fractions
You are viewing a single comment's thread. Return to all comments →
My Stern-Brocot approach takes 0.054 seconds for that sample. Let the "SB enumeration" of a/b be a sequence of Ls and Rs depecting the left and right branches taken in the tree. Then 1/n is a sequence of n-1 Ls. I'm guessing that in your approach, you took one L (or R) at a time. But it's possible to calculate how many Ls (or Rs) to take in a row at each change in direction, thus going from 1/1 to 1/n in a single iteration, instead of n-1 iterations.
Once you find a/b in the Stern-Borcot tree, there are only two possible paths to find the answer (due to the sorted nature of the tree), which can both be found in constant time. The worst case for finding a/b is LRLRLRLR... which corresponds to the Fibonacci numbers; Fib(n) is approximately phi^n, so the algorithm to find a/b is O(log(b)).
I don't want to reveal to much here, but message me if you're still interested in the algorithm.