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.
Solved this problem in F# with the following strategy:
Follow the path in the Stern-Brocot tree by using binary search and medians until you find the target fraction a/b. When you find it, use the target fraction and last left-boundary of the binary search to do more repeated medians until the denominator is greater than N.
What surprises me is that this solution is accepted, while it runs for 50 seconds on an input like
1 1000000000 1000000000000000
If anybody has a solution to this problem that is also efficient for the test case 1 1000000000 1000000000000000 then I would love to hear it!
Thanks
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 →
Solved this problem in F# with the following strategy: Follow the path in the Stern-Brocot tree by using binary search and medians until you find the target fraction a/b. When you find it, use the target fraction and last left-boundary of the binary search to do more repeated medians until the denominator is greater than N.
What surprises me is that this solution is accepted, while it runs for 50 seconds on an input like 1 1000000000 1000000000000000
If anybody has a solution to this problem that is also efficient for the test case 1 1000000000 1000000000000000 then I would love to hear it! Thanks