Project Euler : Sum Of Digits In a^b

The problem no. 16 in Project Euler required us to find the sum of all the digits of the number $2^{1000}$ . Well, a no brainer would be to use the BigInteger and find the number by multiplication. I wanted a better solution.

But my knowledge and wits failed me. I must accept taking help on this one. I googled up a bit and found a very neat way of exponentiation. The basic funda is this:

$2^n = 2 * 2^{n-1}$

$=> 2^n = 2^{n-1} + 2^{n-1}$

So at any given time, if we have an array of digits of say $2^p$ , then getting $2^{p+1}$ is as simple as doubling all the digits and adjusting the carry-overs. The same principle can be easily extended to deal with any base.

Below I have pasted my code which can find the sum of digits for any arbitrary $a^b$ .

public class Problem_16 {
	public long sumOfDigits(int base, int exp) {
		int numberOfDigits = (int) Math.ceil(exp * Math.log10(base));
		int[] digits = new int[numberOfDigits];
		digits[0] = base;
		int currentExp = 1;

		Stopwatch stopwatch = new Stopwatch();
		stopwatch.start();

		while (currentExp < exp) {
			currentExp++;
			int carry = 0;
			for (int i = 0; i < digits.length; i++) {
				int num = base * digits[i] + carry;
				digits[i] = num % 10;
				carry = num / 10;
			}
		}

		long sum = 0;
		for (int digit : digits)
			sum += digit;

		stopwatch.stop();
		System.out.println("The reading for operation is: " + stopwatch);

		return sum;
	}

	public static void main(String[] args) {
		int base = 2;
		int exp = 1000;
		System.out.println(new Problem_16().sumOfDigits(base, exp));
	}
}

Popularity: 5% [?]

Project Euler : Sum Of Digits In a^b

Popular Posts

Recent Posts