UVA – 530 – Binomial Showdown

I first thought of this short working method.


	public static long nCr0(long n, long r) {
		if (r == 0 || n == 1 || n == r)
			return 1;

		return nCr0(n - 1, r - 1) + nCr0(n - 1, r);
	}

but of course it will go to deep and repeated recursion with this problem limits.
so I got ACC with this one

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);

		while (true) {
			int n = in.nextInt(), r = in.nextInt();

			if (n == 0 && r == 0)
				break;
			System.out.printf("%d\n", nCr(n, r));
		}
	}

	public static int gcd(int a, int b) {
		return b != 0 ? gcd(b, a % b) : a;
	}

	public static long nCr(int n, int r) {
		int ans = 1;
		r = r > n / 2 ? n - r : r;
		int fac[] = new int[r];

		for (int i = 0; i < r; i++)
			fac[i] = n - i;

		for (int j = 2, denum = 2, i = 0; j <= r; i = 0, j++, denum = j)
			while (denum > 1) {
				int gcd = gcd(fac[i], denum);
				fac[i++] /= gcd;
				denum /= gcd;
			}

		for (int i = 0; i < r; i++) {
			ans *= fac[i];
		}

		return ans;
	}
}
Advertisements

One thought on “UVA – 530 – Binomial Showdown

  1. Robert Almeyda…

    […]UVA – 530 – Binomial Showdown « Belbesy M. Adel[…]…

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: