3
\$\begingroup\$

Find nCr for given n and r.

Input:

First line contains no of test cases T, for every test case 2 integers as inputs (n,r).

Output:

Compute and print the value in separate line. Modulus your output to 10^9+7. If n

Constraints:

1<=T<=50

1<=n<=1000

1<=r<=800

Example:

Input:

1

3 2

Output:

3

My approach:

import java.util.Scanner;
import java.lang.Math;
import java.math.BigInteger;

class GFG {

    private static int calcBinCoeff (int num, int r) {

        BigInteger numerator = new BigInteger("1");
        int limit = (int)(Math.pow(10,9) + 7);
        BigInteger modulus = new BigInteger(String.valueOf(limit));

        for (int i = num; i > num - r ; i--) {
            BigInteger ind = new BigInteger(String.valueOf(i));
            numerator = numerator.multiply(ind);
        }   

        BigInteger fact = new BigInteger("1");

        for (int i = 2; i <= r; i++) {
            BigInteger elem = new BigInteger(String.valueOf(i));
            fact = fact.multiply(elem);
        }

        BigInteger ans = (numerator.divide(fact)).mod(modulus);

        return ans.intValue();
    }

    public static void main (String[] args) {
        try (Scanner sc = new Scanner(System.in)) {
            int numTests = sc.nextInt();

            while (numTests-- > 0) {
                int num = sc.nextInt();
                int r = sc.nextInt();

                System.out.println(calcBinCoeff(num, r));
            }
        }

    }
}

I have the following questions with regards to the above code:

1.Is there a smarter way to approach this question?

  1. How can I improve the space and time complexity of the given question?

  2. Have I gone too overboard by using BigInteger Library for this question?

Reference

\$\endgroup\$
3
\$\begingroup\$
  • Is there a smarter way to approach this question?

We'll see in a moment. Parts of it can be improved for sure.

  • How can I improve the space and time complexity of the given question?

You can't. The complexity will remain the same. The changes you can make might give small increases in performance or decrease memory usage, but the complexity will remain the same.

  • Have I gone too overboard by using BigInteger Library for this question?

I thought at first that it was possible to use just long, but I'm afraid not. Because of 1000 nCr 500, and such big numbers, you are stuck with BigInteger.


You can use BigInteger.valueOf instead of using the constructor with a String.

You can save some time by using the symmetric property of nCr if r > n / 2. For example, 100 nCr 80 is the same as 100 nCr 20.

You can use just one for-loop instead of two:

value = 1;
for (int i = 0; i < r; i++) {
    value = value * (n - i) / (i + 1);
}
return value;

I used something similar in a project of mine (where I used double instead and thus didn't have to think about truncating integers - an issue which is fixed above thanks to Martin R).

\$\endgroup\$
  • \$\begingroup\$ Yes, 1000 choose 500 will overflow with long. \$\endgroup\$ – aventurin Sep 29 '18 at 12:29
  • 1
    \$\begingroup\$ It should be value = value * (n - i) / (i + 1); so that the intermediate results are integers. But reducing value = value % M in each step could still produce a wrong result, try it with \$ \binom {10}{3} \bmod 17 \$. \$\endgroup\$ – Martin R Sep 29 '18 at 12:31
  • \$\begingroup\$ @MartinR Right, in my own code I was using double. I think I fixed all your points now. \$\endgroup\$ – Simon Forsberg Sep 29 '18 at 13:01
  • \$\begingroup\$ @aventurin Yeah I was fooled by the modulo requirement, but indeed it goes wrong because the value will be multiplied in the next iteration. Fixed that issue now. \$\endgroup\$ – Simon Forsberg Sep 29 '18 at 13:02
  • \$\begingroup\$ @SimonForsberg: Actually it is possible, but you have to multiply with the “modular inverse” of (i+1) instead of dividing by (i+1). (C code here: stackoverflow.com/a/35229199/1187415) \$\endgroup\$ – Martin R Sep 29 '18 at 13:04
3
\$\begingroup\$

I have the following questions with regards to the above code:

  1. Is there a smarter way to approach this question?

  2. How can I improve the space and time complexity of the given question?

  3. Have I gone too overboard by using BigInteger Library for this question?

Yes, as follows, and yes. Consider

Modulus your output to 10^9+7

You seem to have taken that instruction rather literally. Multiplication is not constant time when you're working with BigInteger. If all of the multiplications are carried out instead in longs modulo M=10^9+7 then they become effectively constant time.

This gives you two main options:

  1. Compute the two values you currently compute, modulo M, and then use extended Euclid to compute a multiplicative inverse M (which is prime by design) to perform the division.
  2. Use a simple sieve to compute the prime factorisation of each number up to n; then find the power of each prime independently as \$\nu_p \left(\binom{n}{r}\right) = \nu_p (n!) - \nu_p(r!) - \nu_p((n-r)!)\$ and \$\nu_p(k!) = \sum_{i=1}^k \nu_p(i) \$. Finally multiply together the appropriate prime powers modulo M.

Postscript: it occurs to me that if you take the first of these alternatives, using BigInteger would mean that you don't need to implement Euclid yourself, as you could use BigInteger.modInverse. It would still be advisable to apply mod frequently to keep the size of the integers down, but "to avoid reimplementing the wheel" is a good reason to use BigInteger.

\$\endgroup\$
  • \$\begingroup\$ Thanks, @Peter Taylor. This Math trick didn't enter my head that time!! \$\endgroup\$ – Anirudh Thatipelli Sep 30 '18 at 10:11
3
\$\begingroup\$

Given the product formula

$$\binom nk = \prod_{i=1}^k \frac{n-k+i}{i} \tag1$$

and the symmetry property

$$\binom nk = \binom n{n-k} \tag2$$

of the binomial coefficient, you can implement the calculation in the following way which avoids fractional intermediate values as well as looping more than \$\lfloor \frac{n}{2}\rfloor\$ times.

static final BigInteger MOD = BigInteger.valueOf(1_000_000_007L);

public static BigInteger calcBinCoeff(BigInteger n, BigInteger k)
{
    BigInteger bin; // binomial coefficient
    BigInteger nom; // nominator
    BigInteger den; // denominator

    if (k.shiftLeft(1).compareTo(n) == 1)
        return calcBinCoeff(n, n.subtract(k)); // (2)

    bin = BigInteger.ONE;
    nom = n;
    den = BigInteger.ONE;

    while (den.compareTo(k) < 1) // (1)
    {
        bin = bin.multiply(nom).divide(den);
        nom = nom.subtract(BigInteger.ONE);
        den = den.add(BigInteger.ONE);
    }

    return bin;
}

// 159835829
calcBinCoeff(BigInteger.valueOf(1000), BigInteger.valueOf(800)).mod(MOD);

Using long would overflow for \$1000 \choose 500\$.

Instead of taking the result of calcBinCoeff modulo MOD you could modify the above code and calculate bin modulo MOD in each intermediate step. As @MartinR mentioned in a comment, division must then be replaced by multiplication with the modular inverse of the denominator. This works because 1000000007 is prime and thus coprime to any input in the given range.

public static BigInteger calcBinCoeff(BigInteger n, BigInteger k)
{
    BigInteger bin; // binomial coefficient
    BigInteger nom; // nominator
    BigInteger den; // denominator

    if (k.shiftLeft(1).compareTo(n) == 1)
        return calcBinCoeff(n, n.subtract(k));

    bin = BigInteger.ONE;
    nom = n;
    den = BigInteger.ONE;

    while (den.compareTo(k) < 1)
    {
        bin = bin.multiply(nom).multiply(den.modInverse(MOD)).mod(MOD);
        nom = nom.subtract(BigInteger.ONE);
        den = den.add(BigInteger.ONE);
    }

    return bin.mod(MOD);
}

For the small prime modulus 1000000007 this algorithm also works for long without overflow. A possible implementation is given below.

public static long calcBinCoeff(long n, long k)
{
    long bin; // binomial coefficient
    long nom; // nominator
    long den; // denominator

    if (k + k > n)
        return calcBinCoeff(n, n - k);

    bin = 1;
    nom = n;
    den = 1;

    while (den <= k)
    {
        bin = Math.floorMod(bin * nom, MOD);
        bin = Math.floorMod(bin * modInverse(den, MOD), MOD);
        nom -= 1;
        den += 1;
    }

    return Math.floorMod(bin, MOD);
}

/**
 * The modular inverse as described in
 * https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm
 * @param n A positive number.
 * @param p A prime number.
 * @return The modular inverse
 */
public static long modInverse(long n, long p)
{
    //  i-1   i
    long R,   r; // remainders
    long S,   s; // 1st Bézout coefficients
    long T,   t; // 2nd Bézout coefficients

    assert n > 0 && p > 0;

    R = n;
    r = p;

    S = 1;
    s = 0;

    T = 0;
    t = 1;

    while (r > 0)
    {
        long _q = R / r;
        long _r = R - _q * r;  R = r;  r = _r;
        long _s = S - _q * s;  S = s;  s = _s;
        long _t = T - _q * t;  T = t;  t = _t;
    }

    assert R == 1; // gcd == 1 since p is assumed to be prime

    return Math.floorMod(S, p);
}
\$\endgroup\$
  • \$\begingroup\$ I've overread the 10^9+7 modulus. With than limitation you could actually use long as @MartinR pointed out in another comment. \$\endgroup\$ – aventurin Sep 29 '18 at 13:17
  • \$\begingroup\$ Thanks, @aventurin. That's a very good solution by the way. You have utilised the Math behind nicely. \$\endgroup\$ – Anirudh Thatipelli Sep 30 '18 at 10:17
  • \$\begingroup\$ Beginner question: Isn't using global variables considered bad coding practice, @aventurin? \$\endgroup\$ – Anirudh Thatipelli Sep 30 '18 at 10:30
  • \$\begingroup\$ Yes, generally speaking global variables are considered bad practice. This also holds for Java that does not have a global scope (every variable belongs to a class). An exception from this rule are constants, i.e. variables that could not be reassigned (ˋfinalˋ) and whose state could not be changed (immutable type such as ˋBigIntegerˋ). ˋMODˋ is such a case. \$\endgroup\$ – aventurin Sep 30 '18 at 10:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.