Project Euler #73: Counting fractions in a range Discussions | | HackerRank

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 finally after a couple of failed trials.

For whomever it may help:

The answer for 2 1999999 is about 2*10^11. This is quite a big number, so O(n) where n is the answer will give you a time-out.

Generating the Farey sequence until 1/A will be too slow, for this reason.

One can use the Stern-Brocot tree to traverse all fractions between 1/(A+1) and 1/A. This is faster than generating the Farey sequence, in the sense that you skip all fractions smaller than 1/(A+1). However, it is still too slow (and might give you stack overflows when traversing with a DFS or out of memory when traversing with a BFS). The DFS implementation solved only 10 out of 13 test cases. I was not able to find a smart way to count the requested fractions in the Stern-Brocot sub-tree faster.

Finally, after some research I found this paper: http://people.csail.mit.edu/mip/papers/farey/talk.pdf . Using the formulas and algorithm explained halfway through the paper, one can solve the problem with some DP in O(D log D).

Obviously, don't use doubles when you can use integers. This changed one test case for me from Wrong Answer to Accepted.

Good luck!

PS "Easy" is not the right category for this problem if you ask me...

You can find my java solution here

Solved this problem finally after a couple of failed trials.

For whomever it may help:

Good luck!

PS "Easy" is not the right category for this problem if you ask me...

What is the test case #10? I got a "wrong answer" for #10 only. Thanks!

can any one advice how to get better run time for gcd() function

even though i used the farey sequence in c my time hasent reduced. only 2 test case are accepted.