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.
  • Hackerrank Home
  • Practice
  • Certification
  • Compete
  • Career Fair
  • Hiring developers?
  1. All Contests
  2. ProjectEuler+
  3. Project Euler #71: Ordered fractions
  4. Discussions

Project Euler #71: Ordered fractions

Problem
Submissions
Leaderboard
Discussions

Sort 13 Discussions, By:

votes

Please Login in order to post a comment

  • kitchent
    3 years ago+ 0 comments

    Floating point comparison is disastrous. Use algebraic comparison.

    I followed the recommendation of others and looked up Stern-Brocot tree, Farey neighbours. However, even though I believe I've sufficiently implemented those approaches, it is still TLE #16-#20 in Python.

    Farey neighbours seemed promising with an elegant expression like , but it somehow could not pass all test cases.

    My latest implementation was even optimised with logarithms and extensively used continued fraction representation. When binary search along the Stern-Brocot tree was too slow for an input like 3 1000000000 1000000000000000 because of occasionally looking for gcd to get mediants, I switched to first finding the continued fraction representation of the parent, and get the neighbour fraction from it (the parent itself or the left branch of it whichever applicable).

    I don't know where and how I could further improve my solution, consider it gives result for 3 1000000000 1000000000000000 in about 1 second.

    EDIT: One of the test inputs that requires more time: 100010627 100010633 1000000000000000.

    EDIT 2: Got a very fast solution making use of the concept of Farey neighbours and modular inversion (implemented with Extended Euclidean Algorithm, which I just copied from somewhere else). It looks mythical to me that just with the property , we could get to the answer in a blink of an eye. Very useful when the denominator of input is large. As I know nothing about modular inversion, will definitely come back to it after some reading.

    3|
    Permalink
  • denmatfoton
    6 months ago+ 0 comments

    Here is my solution. Super fast in python 3

    def egcd(a, b):
        if a == 0:
            return (b, 0, 1)
        else:
            g, y, x = egcd(b % a, a)
            return (g, x - (b // a) * y, y)
    
    def modinv(a, m):
        g, x, y = egcd(a, m)
        if g != 1:
            raise Exception('modular inverse does not exist')
        else:
            return x % m
    
    
    t = int(input())
    
    for i in range(t):
        a, b, n = [int(x) for x in input().split()]
        inv_a = modinv(a, b)
        r = n % b
        d = r - inv_a
        if d < 0:
            d += b
        den = n - d
        num = (den * a - 1) // b
        print("{} {}".format(num, den))
    
    1|
    Permalink
  • chenyg
    2 years ago+ 0 comments

    别看下面几位大爷的瞎BB。

    (b*N-1)/(N*X) is a fraction less than b/a. Take the k step continued fraction of the fraction and calculate the denominator of the fraction represented by the continued fraction. Use Binary Search for k in range(1,32).

    1|
    Permalink
  • georeth2010
    3 years ago+ 0 comments

    Accepted by using __int128_t in C++. (only for comparision)

    bool is_less(int64_t x1, int64_t y1, int64_t x2, int64_t y2) {
        return (__int128_t)x1 * y2 < (__int128_t)x2 * y1;
    }
    

    search the answer in continued fraction tree. floating point error will cause problem.

    1|
    Permalink
  • hemanth7787
    6 years ago+ 0 comments

    Farey sequence can be used to generate reduced proper fractions.

    1|
    Permalink
Load more conversations

Need Help?


View top submissions
  • Contest Calendar
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature