Having trouble with the output of this combination in Java

user_13849173 0
Viewed 68

I'm trying to calculate a combination using this formula: formula

I'm running into issues with the output. My program simply outputs 0 when I run this code:

public class Lottery {
    public static long numPossibleTickets(int k, int n, int m) {
        int i;
        int j;
        long numerator = n;
        long denominator = k;
        long total = 0;
        for (i = n - 1; i > (k + 1); i--) {
            numerator = numerator * i;
        }
        i = 0;
        for (j = k; j > 0; j--) {
            denominator = denominator * (denominator - i);
            i++;
        }
        total = m * (numerator / denominator);
        return total;
    }

    public static void main(String[] args) {
        Scanner scnr = new Scanner(System.in);
        int k = 5;
        int n = 69;
        int m = 26;
   System.out.println(numPossibleTickets(k, n, m));
    }
}

However, the output should be 292,201,338. Any help with this would be much appreciated. Thanks so much!

combinations java
2 Answers

I'd prefer to create a method to get the factorial of a number. besides also using a BigInteger as long isn't enough to store big numbers factorial so here's final code and it's working

public static void main(String[] args) {

    int k = 5;
    int n = 69;
    int m = 26;
    System.out.println(numPossibleTickets(k, n, m)); // result is 292201338
}
public static BigInteger numPossibleTickets(int k, int n, int m) {
    int i;
    int j;
    BigInteger numerator =  getFactorial(n);
    BigInteger denominator = getFactorial(k).multiply(getFactorial(n-k));
    BigInteger total ;

    total = new BigInteger(m+"").multiply(numerator.divide(denominator));
    return total;
}

// to get the factorial of given number 
public static BigInteger getFactorial(int number){
    BigInteger factorial = new BigInteger(number+"");
    for (int i = number - 1; i > 1; i--) {
        factorial = factorial.multiply(new BigInteger(i+""));
    }
    return  factorial;
}
user_62859730

There are at least 3 different problems with your code.

You are trying to compute the number of combinations using factorials. The problem with factorial is that it grows incredibly fast: the intermediate results don't fit in the range for the long data type, and the result is useless. You could use the BigInteger for the computations, but it won't be particularly efficient. With that change:

public static long numPossibleTickets(int k, int n, int m) {
    int i;
    int j;
    BigInteger numerator = BigInteger.valueOf(n);
    BigInteger denominator = BigInteger.valueOf(k);
    long total = 0;
    for (i = n - 1; i > (k + 1); i--) {
        numerator = numerator.multiply(BigInteger.valueOf(i));
    }
    i = 0;
    for (j = k; j > 0; j--) {
        denominator = denominator.multiply(denominator.subtract(BigInteger.valueOf(i)));
        i++;
    }
    total = m * numerator.divide(denominator).longValue();
    return total;
}

Second, the loop that computes the numerator is off by one: instead of computing 69!/5! it's computing 69!/6!. Luckily that's easy to fix:

    for (i = n - 1; i >= (k + 1); i--) {
        numerator = numerator.multiply(BigInteger.valueOf(i));
    }

Third, the loop that computes the denominator seems to be way off. I don't know what you're trying to do, but given what you are computating for the numerator, the denominator should be computing (n-k)!, and that could look like this:

    BigInteger denominator = BigInteger.ONE;
    for (int j = n-k; j > 1; j--) {
        denominator = denominator.multiply(BigInteger.valueOf(j));
    }

With these three changes, I get the expected output 292201338.

user_3187580
Related