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
  • Prepare
    NEW
  • Certify
  • Compete
  • Career Fair
  • Hiring developers?
  1. Prepare
  2. Mathematics
  3. Fundamentals
  4. Matrix Tracing
  5. Discussions

Matrix Tracing

Problem
Submissions
Leaderboard
Discussions
Editorial

    You are viewing a single comment's thread. Return to all comments →

  • chetbhateja
    1 year ago+ 1 comment

    Just for fun, a code golf solution in Python:

    def solve(n, m):
        inv=lambda a,b,c,d:(b<2)*d or inv(b,a%b,d,c-a//b*d)
        p,q,C=1,1,10**9+7
        for i in range(m,n+m-1):
            p,q=p*i%C,q*(i-m+1)%C
        return p*inv(q,C,1,0)%C
    

    To avoid timing out this uses the factorial formula for the choose function, modding out at each step so that multiplication does not become too costly. Note that building tables can take quadratic time while the formula takes linear time. To tackle the division in the formula inside the modulus, a modular inversion function based on the Euclidean algorithm is written on the first line.

    2|
    Permalink
  • Contest Calendar
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature