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

    HackerRank

  • |
  • Prepare
  • Certify
  • Compete
  • Apply
  • Hiring developers?
  1. Prepare
  2. Mathematics
  3. Fundamentals
  4. Matrix Tracing
  5. Discussions

Matrix Tracing

Problem
Submissions
Leaderboard
Discussions
Editorial

Sort 51 Discussions, By:

recency

Please Login in order to post a comment

  • haricung
    10 months ago+ 0 comments

    TLE'd on this but i was thinking somewhere along the lines of the followng: nc = int(math.factorial(m)//(math.factorial(r)*math.factorial(m-r))) where r in range(n)

    0|
    Permalink
  • macdonald_l_kyn
    12 months ago+ 0 comments

    My python3 solution but time limit execution

    def solve(n):
        if n == 0:
            return 1
        i = 5
        while True:
            if (n*"0") in str(math.factorial(i)):
                return i
            i += 1
    
    0|
    Permalink
  • stzong1
    1 year ago+ 0 comments
    import math
    import os
    import random
    import re
    import sys
    
    mod = 10**9 + 7
        
    def getfactmod(b):
      val = 1
      for i in range(1,b):
        val =((val%mod)*((i+1)%mod))%mod
      return val
        
    def getpowermod(a,b):
        result = 1
        while b:
            if b%2 == 1:
                result = (result%mod * a%mod) % mod
            a = a%mod * a%mod
            b = b//2
        return result
            
    def solve(x,y):
        num = getfactmod(x+y-2)
        denom = getfactmod(x-1)*getfactmod(y-1)
        return ((num%mod)*(getpowermod(denom,mod-2)))%mod
      
    if __name__ == '__main__':
        fptr = open(os.environ['OUTPUT_PATH'], 'w')
    
        t = int(input().strip())
    
        for t_itr in range(t):
            first_multiple_input = input().rstrip().split()
    
            n = int(first_multiple_input[0])
    
            m = int(first_multiple_input[1])
    
            result = solve(n, m)
    
            fptr.write(str(result) + '\n')
    
        fptr.close()
    
    0|
    Permalink
  • soumyadipmandal2
    1 year ago+ 1 comment

    As there involves many large numbers in each test case, so applying the formula C ( m+n-2, m-1) or C (m+n-2, n-1) directly will not work.

    We have to use a bit of number theory here.

    To find the factorial of a number, n!, instead from 1 to n, we also have to mod put the value at each step of multiplication so that the multiplication becomes fast.

    According to fermat's little theorem, a ** ( p - 1 ) == 1 mod( p )

    ==> ( a ** ( p - 1 ) ) * ( a ** ( -1 )) == a ** ( -1 ) mod( p )

    ==> a ** ( p - 1 - 1 ) == a ** ( -1 ) mod( p )

    ==> a ** ( p - 2 ) == a ** ( -1 ) mod( p )

    ==> a ** ( -1 ) == a ** ( p - 2 ) mod( p )

    0|
    Permalink
  • kevalgada12
    2 years ago+ 1 comment

    i found a very easy answer......fact(r+c-2)/(fact(r-1)*fact(c-1))...............can someone verify

    0|
    Permalink
Load more conversations

Need Help?


View editorial
View top submissions
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy