echoblaze - 6 months ago 28

Java Question

... preferably in Java. Here is what I have:

`//x choose y`

public static double choose(int x, int y) {

if (y < 0 || y > x) return 0;

if (y == 0 || y == x) return 1;

double answer = 1;

for (int i = x-y+1; i <= x; i++) {

answer = answer * i;

}

for (int j = y; j > 1; j--) {

answer = answer / j;

}

return answer;

}

I'm wondering if there's a better way of doing this?

Answer

choose(n,k) = n! / (n-k)! k!

You could do something like this in O(k):

```
public static double choose(int x, int y) {
if (y < 0 || y > x) return 0;
if (y > x/2) {
// choose(n,k) == choose(n,n-k),
// so this could save a little effort
y = x - y;
}
double denominator = 1.0, numerator = 1.0;
for (int i = 1; i <= y; i++) {
denominator *= i;
numerator *= (x + 1 - i);
}
return numerator / denominator;
}
```

**EDIT** If `x`

and `y`

are large, you will overflow more slowly (i.e., be safe for larger values of x & y) if you divide your answer as you go along:

```
double answer = 1.0;
for (int i = 1; i <= y; i++) {
answer *= (x + 1 - i);
answer /= i; // humor 280z80
}
return answer;
```