Skip to content
April 17, 2011 / oop123

Project Euler #104 – Java

You can see the problem here: Problem #104.

I brute-forced the question… I didn’t know there was a formula for calculating the nth term for the Fibonacci sequence without calculating all the terms before it! Well, truth to be told, I had read something like that before in a book, but I forgot about it. Sigh. Anyway, this is (kind of) hard because you need to keep track of the first nine digits of the Fibonacci sequence, and I have no idea how to do that without calculating the whole sequence. I resorted to brute-forcing it.

I tested BigInteger and its toString() with a simple loop and found it’s just too slow. Even for the first 20000 Fibonacci numbers, it was already taking 1 second. I resorted to writing an array that would keep track of each part (9 digits long) of the Fibonacci number. Other than that, the logic is pretty simple – keep calculating the Fibonacci numbers until I solved the question.

int[] partsA = new int[50000], partsB = new int[50000],
       cache10 = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000};
int count = 1, temp;
			
//initialize fibonacci sequence
partsA[0] = 1;
partsB[0] = 1;
			
//carry flag
boolean carry = false;

//since the minimum possible answer is 2750, get the sequence until 2750
for (int i = 3; i < 2750; i++) {
	carry = false;
	
	for (int j = 0; j < count; j++) {
		temp = partsA[j];
		partsA[j] = partsB[j];
		partsB[j] = partsB[j] + temp;
	
		//if there is carry from last calculation, add 1 to current digit
		if (carry == true) { partsB[j]++; }
		
		//if current number is bigger than the limit, then set carry flag to true
		//else there is no carry
		if (partsB[j] > 1000000000) {
			//increase the number of array use to hold the numbers
			if (partsB[j + 1] == 0) { count++; }
	
			partsB[j] -= 1000000000;
			carry = true;
		} else {
			carry = false;
		}
	}
}

			
for (int i = 2750; ; i++) {
	carry = false;

	for (int j = 0; j < count; j++) {
		temp = partsA[j];
		partsA[j] = partsB[j];
		partsB[j] = partsB[j] + temp;
	
		//if there is carry from last calculation, add 1 to current digit
		if (carry == true) { partsB[j]++; }
		
		//if current number is bigger than the limit, then set carry flag to true
		//else there is no carry
		if (partsB[j] > 1000000000) {
			//increase the number of array use to hold the numbers
			if (partsB[j + 1] == 0) { count++; }
	
			partsB[j] -= 1000000000;
			carry = true;
		} else {
			carry = false;
		}
	}

	if (isPandigital9(partsB[0])) {
		//get the first nine digits
		int number = partsB[count - 1],
		    digitsNum = DLNumber.numOfDigitsOf(<span class="hiddenGrammarError" pre="">number);
		number</span> = number * cache10[9 - digitsNum];
		number += partsB[count - 2] / cache10[digitsNum];
		if (isPandigital9(number)) {
			System.out.println("***" + number + ": " + i);
			break;
		}
	}
}

isPandigital9() is very easy to implements (all the .digitOf() and .numOfDigitsOf() are methods I wrote before. I think they are very fast…).

private static boolean isPandigital9(int number) {
	int[] digits = DLNumber.digitsOf(number);
	boolean[] check = new boolean[10]; check[0] = true;
	for (int i = 0, len = digits.length; i < len; i++) {
		if (check[digits[i]]) {
			return false;
		}
		else {
			check[digits[i]] = true;
		}
	}
	return true;
}

Runs in 20 seconds on my computer. Sigh. Anyway, if I only had known that there was a way to calculate the nth Fibonacci number without calculating the previous numbers. It would’ve hundreds of time faster.

Oh, well. I really didn’t want to brute force it, but I still finish it within a reasonable time (not really), so all’s good. CU

Advertisements

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: