top button
Flag Notify
    Connect to us
      Site Registration

Site Registration

Best way to calculate nCr mod m

+3 votes
956 views

How to implement a function which calculates nCr mod m considering
m = 10^5
1<= r <= n <= 10000

Main issue is data overflow. Can be done using Java Big Integers but that is time intensive.

Thanks !

posted Jan 3, 2014 by Pankaj Agarwal

Share this question
Facebook Share Button Twitter Share Button LinkedIn Share Button

1 Answer

+1 vote

See this property

nCr = n-1Cr + n-1Cr-1

So

 nCr mod m = (n-1Cr mod m + n-1Cr-1 mod m) mod m

Now mix recursion with the above property and let me know if you need complete function in C or C++.

answer Jan 3, 2014 by Salil Agrawal
Similar Questions
0 votes

suppose

A(n,m) = 
1 2 3         
4 5 6                            
7 8 9

and 

B(p, q) = 
1 1
1 1

What is best method to find min of square of difference of sub-matrices of A and B e.g.

sub-matrices of A =

1 2    |     2 3   |    4 5    |   5 6
3 4    |     5 6   |    7 8    |   8 9

Difference of first sub-matrix of A with B =

(1-1)  (2-1)    = |     0 1
(3-1)  (4-1)      |     2 3

sum of square of elements = 0*0 + 1*1 + 2*2 + 3*3 = 14

similar steps for other sub-matrices of A

Please suggest looking for an alternate method or algorithm which has time complexity less than O(n*m*p*q)

+4 votes

Two numbers a and b are said to be co-prime if gcd(a,b) is 1.

Now my question is about the algorithm to find out if given two numbers are co-prime.

+2 votes

convert a number m to n with minimum operations. The operations allowed were -1 and *2.

For Eg : 4 and 6. Answer is 2.
1st operation : -1 -> 4-1 = 3.
2nd operation : * -> 3 * 2 =6.

+2 votes

Calculate all permutations for an array of integers.

For example: Given {3, 5, 8} - Output should be: { 3, 5, 8 }, { 3, 8, 5 }, { 5, 3, 8 }, { 5, 8, 3 }, { 8, 5, 3 }, { 8, 3, 5 }

...