Project Euler/53

https://charlesreid1.com:3000/cs/euler/src/master/scratch/Round2_050-070/053

Code

public class CombinatoricSelections {
	public static void main(String[] args) { 
		doit();
	}

	/** Nice easy test. This should be bigger than 1 million - should return true. */
	public static void test() { 
		System.out.println("isBigger(23,10) = "+isBigger(23,10));
	}

	/** Solve the problem. */
	public static void doit() {
		int MAX = 100;
		int count = 0;
		boolean[][] isBig = new boolean[MAX][MAX];
		for(int nm1=0; nm1<MAX; nm1++) { 
			for(int rm1=0; rm1<MAX; rm1++) { 
				// determine if n C r > 1M
				int n = nm1+1;
				int r = rm1+1;
				boolean big = isBigger(n,r);
				isBig[nm1][rm1] = big;
				if(big) count++;
			}
		}
		System.out.println("Total number of n Choose r values that are greater than 1M: "+count);
	}

	/** Boolean: is n choose r bigger than 1 million? */
	public static boolean isBigger(int n, int r) {
		int d = (n-r);
		double LHS = 0.0;
		for(int j=0; j<d; j++) {
			LHS += Math.log(r+d-j) - Math.log(d-j);
		}
		double RHS = Math.log(1000000);
		return LHS > RHS;
	}
}