Avoiding Complexities When Necessary, Redux.

by Gilbert Keith

There are exactly ten ways of selecting three from five, 12345:

123, 124, 125, 134, 135, 145, 234, 235, 245, and 345

In combinatorics, we use the notation, 5C3 = 10.

In general,

[describes a combination]

It is not until n = 23, that a value exceeds one-million: 23C10 = 1144066.

How many, not necessarily distinct, values of  nCr, for 1 ≤n≤ 100, are greater than one-million?

Attempt one:

import java.math.BigInteger;
import java.util.ArrayList;

public class Problem53 {

	/**
	 * @param args
	 */
	static long beginTwo = System.currentTimeMillis();
	public static BigInteger[] factorialArr;
	static long endTwo;
	public static void populateFactorialArr(int j) {

		factorialArr = new BigInteger[j+1];
		factorialArr[0]=BigInteger.valueOf(1);
		BigInteger factorialVal = Factorial.bigIntFactorial(j);
		for (int i=j; i>0; i--) {
			factorialArr[i]=factorialVal;
			factorialVal=factorialVal.divide(BigInteger.valueOf(i));
		}
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		ArrayList answerList = new ArrayList();
		BigInteger oneMillion = new BigInteger("1000000");
		populateFactorialArr(100);
		for (int n = 23; n<101; n++) {
			for (int r=2; r<(n-1);r++) {

				BigInteger combination = factorialArr[n].divide(factorialArr[r].multiply(factorialArr[(n-r)]));
				if ((combination.compareTo(oneMillion) == 1)) {
					answerList.add(combination);
				}
			}
		}
		System.out.println("Answer: " + answerList.size());
		System.out.println("Time: " + ((endTwo=System.currentTimeMillis())-beginTwo) + " ms");
	}
}

This one runs in: 75-85 ms.

Attempt two:


public class Problem53OtherWay {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		long begin = System.currentTimeMillis();
		int startInt = 23;
		int finalInt = 100;
		int count = 0;
		int maxCount = (((finalInt+1)*(finalInt+2)/2)-((startInt)*((startInt+1)/2)));
		for (int n=23; n< 101; n++) {
			int r=0;
			long numer=1L;
			long denom = 1L;
			long val = 1L;
			do {
				if (r==0) {
					numer = 1;
					denom = 1;
				}
				else {
					numer *= (n-(r-1));
					denom *= r;
				}
				val = numer/denom;
				if (val > 1000000) break;
				count+=2;
				r++;
			} while (r<n);
		}
		System.out.println("Answer: " + (maxCount-count));
		long end;
		System.out.println("Tim: " + ((end = System.currentTimeMillis())-begin) + " ms");
	}

}

This one runs in: 0 ms!

Again: don’t compute things when you don’t have to. I’m glad I figured this out by myself. 🙂

 

Advertisements