# Project Euler #73: Counting fractions in a range

# Project Euler #73: Counting fractions in a range

ErikTillema + 1 comment 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...

kitchent + 0 comments `n // A`

being the count of fractions with denominator`A`

where was a key insight I've failed to notice for a long time. I was also thinking "Easy" is crazy for such a problem which takes pages of editorial on the official site.In retrospect, to begin with this concept in mind, figuring out the removal of fractions in non-reduced form would be straightforward, consider we should have been very familiar with similar techniques from prime sieve, Totient function and more generally, dynamic programming.

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

shashank21jHackerRank AdminChallenge Author + 1 comment use something else then

naseer036 + 0 comments I'm completely new to c n still learning. It would be a great help if u could point me in the right direction.

No more comments

Sort 4 Discussions, By:

Please Login in order to post a comment