Skip to content
September 3, 2011 / oop123

Project Euler #159 – Java

You can see the problem here: Problem #159.

This is my 100th question, woot! Now I just need to complete another 50 questions to become level 4. I doubt I can do another 20 questions, let alone 50, but I will try anyway. Now that little “celebration” is over with, let’s get back to the question. This question is pretty easy. The digital root of a number (in base 10) can be found using the following piecewise function (I love google):

f(n) = \begin{cases}    n\ (mod\ 9) & n\ (mod\ 9) \neq 0 \\    9 & n\ (mod\ 9) = 0  \end{cases}

In plain English, for any number n, find the remainder after dividing n by 9. The digital root of n will be the remainder, unless the remainder is 0, in which case the digital root is 9. Kudos for you if you know why this works (it’s not that hard, hint: it’s related to the fact if a number’s digit sum is divisible by 9, then the number itself is divisible by 9).

The maximal Digital Root Sum (MDRS) of each number can be found with dynamic programming since you can start with the MDRS of small numbers and use them to find the MDRS of the bigger numbers. For those of you who can’t google, dynamic programming involves solving complex problem by breaking it down into sub-problems (usually smaller version of the bigger problem) and doing those instead.

final int SIZE = 1000000;
int[] drs = new int[SIZE];
for (int i = 2; i < SIZE; i++) {
	//prime number: mdrs = digital root
	if (drs[i] == 0) {
		drs[i] = i % 9;
		if (drs[i] == 0) drs[i] = 9;
	}
	//a number's digital root can be its mdrs
	else if (drs[i] < 10) {  //a single number's digital root cannot exceed 10
		int candidate = i % 9;
		if (candidate == 0) candidate = 9;
		drs[i] = Math.max(drs[i], candidate);
	}
	
	int currentNum = i;
	for (int factor = 2; factor <= i; factor++) {
		currentNum += i;
		if (currentNum >= SIZE) break;
		drs[currentNum] = Math.max(drs[i] + drs[factor], drs[currentNum]);
	}
}

//find answer
int sum = 0;
for (int num : drs) sum += num;
System.out.println(sum);

Runs in around 225 milliseconds on my computer. 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: