1

I have to find the value nCr%m where 0 < r < 10^6 and 0 < n < 10^18 and m is a prime (for sake of convenience 10^9+7)

I have read various articles where we can find nCr%m in O(1) time if n<10^6 by pre-calculating the factorial and multiplicative inverse from 1 to n.

My question:-

Now is there any solution to find nCr%m in O(1) time or better than O(r) (if n<10^18) (above trick fails as we cannot store the factorial n is too large for array size).

My solution:-

I have found O(r) solution by finding

numerator-->n*(n-1)(n-2)...(n-r)

denominator-->1*2*3*4*5......r

ans=numerator*multiplicative_inverse(denominator)%mod

nil96
  • 313
  • 1
  • 3
  • 12
  • This may be a better fit for the CS or Math SE. But interesting question. – CompuChip Feb 09 '16 at 09:46
  • yeah thinking very hard........... – nil96 Feb 09 '16 at 09:59
  • 2
    I don't think that there exist a `O(1)` algorithm. You could either calculate it in `O(r)` with `O(1)` precomputations or for `O(1)` with `O(min(n, m))` precomputations. – sve Feb 09 '16 at 10:06

0 Answers0