0

The question was to calculate the number of binomial coefficients not divisible by a given prime number. For example:

For num = 5 and prime = 5, the output should be:

countingBinomialCoefficient(num, prime) = 17

N = 0: [1]
N = 1: [1, 1]
N = 2: [1, 2, 1]
N = 3: [1, 3, 3, 1]
N = 4: [1, 4, 6, 4, 1]
N = 5: [1, 5, 10, 10, 5, 1]

In the above example only 5, 10, 10, 5 are only divisible out of the 21 numbers. So the output is 17

The code I wrote is as follows:

long countingBinomialCoefficient(int num, int prime) {
    long count = 0;
    for (int i = 0; i <= num; i++) {
        long nCk = 1;
        for (int j = 0; j <= i; j++) {
            if (nCk % prime != 0) count++;
            nCk = nCk * (i - j) / (j + 1);
        }
    }
    return count;
}

This proper output for two cases:
1. countingBinomialCoefficient(5, 5) = 17
and
2.countingBinomialCoefficient(5, 7) = 21

But it says time limit(=3000 ms) exceeded in case of
countingBinomialCoefficient(999999999, 7) in which case output should be 2129970655314432
Is there any error in my code? Are there any other shorter methods for this? Please help. Thanks in advance.

FlarrowVerse
  • 197
  • 2
  • 13
  • There is no error in your code (except some number overflow for larger binomial coefficients), but it uses a naive algorithm that takes very long for larger n. You need to find a better method. Experiment with paper and pencil, marking the numbers not divisible by the prime and see if you can find a pattern. This should allow you to get the count without looking at every number. – Henry May 07 '17 at 07:22
  • Well it sounds reasonable to me that if you have a double loop `O(n^2) `code with `n=1b` it might take a while... – Yossi Vainshtein May 07 '17 at 07:22

1 Answers1

0

To reduce the computation time of this code, you can first replace the outer loop with a parallel stream. This can cut the time in half or more.

To further reduce the time, you can share the computation between different machines by dividing the range of rows for the computation and summing the results.

static long countingBinomialCoefficient(int num, int prime) {
    return IntStream.rangeClosed(0, num)
            .parallel()
            .mapToLong(i -> {
                long count = 0;
                long nCk = 1;
                for (int j = 0; j <= i; j++) {
                    if (nCk % prime != 0) count++;
                    nCk = nCk * (i - j) / (j + 1);
                }
                return count;
            }).sum();
}

// test failed in my case on one computer
public static void main(String[] args) {
    long time = System.currentTimeMillis();
    System.out.println(countingBinomialCoefficient(99999, 7)); // 2214367021
    System.out.println(System.currentTimeMillis() - time); // 24941
}

See also: Parallelized Matrix Multiplication