Archive for the 'Problems' Category

Page 4 of 5

Project Euler : A 1000 Digit Fibonacci Number

Published on January 8, 2010 in Problems. 4 Comments

The 25th problem in Project Euler asks the user to find the first fibonacci number which has 1000 digits. I brute forced the solution using the BigInteger class of java to find the solution. Here’s the code:

package problems_21_30;

import java.math.BigInteger;

public class Problem_25 {
	public static void main(String[] args) {
		BigInteger[] number = new BigInteger[3];
		number[0] = BigInteger.ONE;
		number[1] = BigInteger.ONE;
		int index = 1;
		int count = 2;
		while (number[index].toString().length() < 1000) {
			index = (index + 1) % 3;
			number[index] = number[(index + 2) % 3].add(number[(index + 1) % 3]);
			count++;
		}
		System.out.println(count);
	}
}

Popularity: 22% [?]

Project Euler : Finding The nth Digit Of The Fractional Part Of Irrational Number

Published on January 5, 2010 in Problems. 0 Comments

The Problem 40 of Project Euler required just a pencil and a paper to get the answer. We are given an irrational decimal fraction by concatenating consecutive integers:

0.123456789101112131415 …

The $12^{th}$ digit of this irrational number is 1 and is denoted as $d_{12}$ . The problem requires us to determine the product:

$d_1$ x $d_{10}$ x $d_{100}$ x $d_{1000}$ x $d_{10000}$ x $d_{100000}$ x $d_{1000000}$

A simple enumeration of digits and their positions works out easily.

To begin with, there are only 9 single digit numbers, namely, 1 – 9. So the first 9 places are occupied by single digit numbers. Next, there are 90 double digit numbers from 10 – 99. So these occupy a total of 180 places. We have now accounted for 189 places in out irrational number.

Determine the digits $d_{100}$ and $d_{1000}$ are as simple as illustrated below:

For $d_{100}$ :

Excess from last known digit position = 100 – 9 = 91

Numbers crossed in 91 positions = 91 / 2 = 45

Since the remainder is 1, we want the 1st digit of the 46th number from the one that appeared on position 9.

Thus the number we seek is 9 + 46 = 54, and the digit is therefore 5.

For $d_{1000}$ :

Excess from last known digit position = 1000 – 189 =18 1

Numbers crossed in 811 positions = 811 / 3 = 270

Since the remainder is 1, we want the 1st digit of the 271st number from the one that appeared on position 189.

Thus the number we seek is 99 + 271 = 370, and the digit is therefore 3.

Repeating the same for all the digits we needed, the result is:

$d_{1}$ = 1

$d_{10}$ = 1

$d_{100}$ = 5

$d_{1000}$ = 3

$d_{10000}$ = 7

$d_{100000}$ = 2

$d_{1000000}$ = 1

Thus the product is 210

Popularity: 7% [?]

Project Euler : Verifying Triangle Words

Published on January 5, 2010 in Problems. 0 Comments

Problem 42 in Project Euler provides a list of some 2000 English words and requires us to find the number of triangle words. I went about in a simple straight forward way attempting this one. A class TriangleNumbers keeps a sorted list of all the triangle numbers. A static method in EnglishWord class returns the word value for the given word. This number is checked for validity.

Obviously, new triangle numbers are only computed when the word value is greater than the last known triangle number. An implementation in Java is provided below:

The EnglishWord class:

package pba.text;

/**
 * A class which allows manipulations with the English Words
 *
 * @author AnuvratSingh
 */
public class EnglishWord {
	/**
	 * Returns the numerical value of a word which is found by summing the alphabetical position of each character in
	 * the word. For example, the word value for SKY is 19 + 11 + 25 = 55
	 *
	 * @param word the word whose numerical value is required
	 * @return the numerical value of the given word
	 */
	public static int getNumericalValue(String word) {
		String lowerCaseWord = word.toLowerCase();

		int sum = 0;
		for (int i = 0; i < lowerCaseWord.length(); i++)
			sum += lowerCaseWord.charAt(i) - 'a' + 1;

		return sum;
	}
}

The TriangleNumbers class:

package pba.number;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * The n^(th) term of the sequence of triangle numbers is given by, t_(n) = ½n(n+1); so the first ten triangle numbers
 * are: 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...
 *
 * @author AnuvratSingh
 */
public class TriangleNumbers {
	/**
	 * The list of all triangle numbers in ascending order. The order is not enforced, but required at certain places.
	 */
	private List<Integer> m_triangleNumbers;

	/**
	 * The last number which has been added to the list.
	 */
	private int m_lastNumber;

	/**
	 * The index of the last number which has been inserted.
	 */
	private int m_lastIndex;

	public TriangleNumbers() {
		m_triangleNumbers = new ArrayList<Integer>();
		m_lastIndex = 0;
		m_lastNumber = 0;
	}

	/**
	 * Builds the list of triangle numbers
	 *
	 * @param looseUpperBound The upper bound to which the list is to be created. Loose implies that the last number to
	 *            be inserted into the list will be equal to or just greater than the upper bound specified
	 * @return true if the upper bound is a triangle number itself, false otherwise
	 */
	private boolean buildTriangleNumbers(int looseUpperBound) {
		while (m_lastNumber < looseUpperBound) {
			m_lastNumber += ++m_lastIndex;
			m_triangleNumbers.add(m_lastNumber);
		}
		return m_lastNumber == looseUpperBound ? true : false;
	}

	/**
	 * Check if the given number is a triangle number or not.
	 *
	 * @param number The number for which the condition needs to be verified
	 * @return true if the given number is a triangle number, false otherwise
	 */
	public boolean checkForTriangularNumberProperty(int number) {
		if (number > m_lastNumber)
			return buildTriangleNumbers(number);

		return Collections.binarySearch(m_triangleNumbers, number) >= 0 ? true : false;
	}
}

The main method:

package problems_40_50;

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;

import pba.number.TriangleNumbers;
import pba.text.EnglishWord;

public class Problem_42 {
	private static final String fileName = "problem_42.in";

	public static void main(String[] args) throws IOException {
		TriangleNumbers tn = new TriangleNumbers();

		// Read all the words into a String array
		BufferedReader bufferedReader = new BufferedReader(new FileReader(Problem_42.fileName));
		String[] words = bufferedReader.readLine().split("\",\"");

		// Correct the first and the last word which have "
		int numberOfTriangleWords = 0;
		words[0] = words[0].substring(1);
		int numberOfWords = words.length;
		String lastWord = words[numberOfWords - 1];
		words[numberOfWords - 1] = lastWord.substring(0, lastWord.length() - 1);

		// Check the condition for each word
		for (String word : words)
			if (tn.checkForTriangularNumberProperty(EnglishWord.getNumericalValue(word)))
				numberOfTriangleWords++;

		System.out.println(numberOfTriangleWords);
	}
}

Popularity: 9% [?]

Project Euler : Number Of Routes From One Corner To Another In A Grid

Published on December 22, 2009 in Problems. 0 Comments

I have gone in a very round about way, and my explanation might not be clear. Apparently, this is a very standard combinatorics problem and can be answered at sight. Well, I did not know that, and did a few things which made me realize the combinatorial answer.

The latest problem that I solved was is Problem 15. Given a grid of 20 x 20 squares, the question asked was to find the number of routes from the top left hand corner of the grid to the bottom rightmost corner without ever backtracking.

This was an easy one too. I started out by writing at every meeting point of lines, the number of extra lines that spring out of the point. For example, at the starting point 2 lines start. Select for example the horizontal one. At the first point that it comes across, it forks into 2 lines, which is 1 extra. So I wrote 1 at this point. The same is done at all points except those on the rightmost vertical and the bottommost horizontal which contains the total number of lines passing through it.

Below is a diagram showing the same thing.

Notice the similarity with Pascal’s triangle.

1 1

1 2 1

1 3 3 1

1 4 6 4 1

1 5 10 10 5 1

1 6 15 20 15 6 1

The center element of Pascal’s triangle is given by $^{n}C_{\frac{n}{2}}$ . Our answer in the case of 3 x 3 squares is given by $^{6}C_{3}$ .

Thus our answer for 20 x 20 grid is $^{40}C_{20}$ .

Popularity: 6% [?]

Project Euler : Maximum Sum Traversing Top To Bottom In A Triangle

Published on December 19, 2009 in Problems. 19 Comments

The 18th and the 67th problems in Project Euler are one and the same. The only difference is in the input test case. The problem 18 has a smaller input and 67 has a large input. For the explanation purpose, I’ll consider problem 18. The code without any modification can be extended to 67th problem.

Given a triangle of numbers, the objective is to determine the maximum sum along paths descending from the apex of the triangle to the base. Consider the example:

7 4

2 4 6

8 5 9 3

The maximum sum occurs along the path 3-7-4-9.

The problem required us to determine the maximum sum for any given triangle. Also an interesting thing is mentioned about the problem, in case you were considering a brute force method of checking every path:

It is not possible to try every route to solve this problem (where the base of the triangle has 100 numbers), as there are 2⁹⁹ altogether! If you could check one trillion (10¹²) routes every second it would take over twenty billion years to check them all. There is an efficient algorithm to solve it. ;o)

Being forewarned, I never once gave a thought to the brute force solution.

This problem was not as tricky as they tried to sound it. The solution is quite easy to see. I’ll run you through the idea as it formed in my mind. I used the top-to-bottom approach for forming the idea and coming up with the solution, and then implemented the solution in bottom-to-top sweep. I hope you have realized that a greedy solution will not work here.

Consider the triangle given above. I’ll work out the maximum path for it from top to bottom. We start with 3. We may choose either 7 or 4. To help make this choice, consider the two triangles with apex 7 and the other with 4. So we have two smaller triangles of height 3 each. Say the maximum length for the triangle with apex 7 is x and with apex 4 is y. If x > y, we choose 7 as the next on the path, else 4.

Thus, at every step we form two triangle of height 1 smaller, and choose the apex which has the larger sum. Implemented as it is will give us the recursive solution. To get an iterative solution to this problem, one could traverse from bottom-to-top. The bottom-to-top approach is also simple. It is greedy in approach.

Consider the penultimate row, specifically the triangle with 2 as apex and 8, 5 as the base. The maximum sum in this triangle is 2+8 = 10. Replace 2 with 10. Do the same for all the triangles formed with the penultimate layer as the apex. Thus our triangle reduces to

7 4

10 13 15

You know what to do next. Keep applying the same till the apex of the original triangle has the maximum sum.

I have implemented the bottom-to-top method so as to avoid recursion. Here is my code:

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;

public class Problem_18 {
	private static int heightOfTree = 100;
	private final String fileName = "problem_67.in";
	private int[][] tree;

	public int maxValue() throws IOException {
		readTree();

		for (int i = Problem_18.heightOfTree - 2; i >= 0; i--)
			for (int j = 0; j <= i; j++)
				tree[i][j] += tree[i + 1][j] > tree[i + 1][j + 1] ? tree[i + 1][j] : tree[i + 1][j + 1];

		return tree[0][0];
	}

	private void readTree() throws IOException {
		tree = new int[Problem_18.heightOfTree][];

		BufferedReader bufferedReader = new BufferedReader(new FileReader(fileName));
		for (int i = 0; i < Problem_18.heightOfTree; i++) {
			tree[i] = new int[i + 1];
			String[] values = bufferedReader.readLine().split(" ");
			for (int j = 0; j <= i; j++)
				tree[i][j] = Integer.parseInt(values[j]);
		}
	}

	public static void main(String[] args) throws IOException {
		System.out.println(new Problem_18().maxValue());
	}
}

Popularity: 100% [?]

Project Euler : Longest Sequence Using A Number Under Million

Published on December 19, 2009 in Problems. 1 Comment

Problem number 14 of Project Euler gave a sequence.

n = n/2 if (n is even)

n = 3*n+1 (if n is odd)

It has been observed that all the numbers in this sequence do end up at 1, though this is yet to be proved! For example, if we consider the number 13, then the sequence pans out as

13 -> 40 -> 20 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1

The length of the sequence in this case is 9. The challenge was to find the largest starting number below 1 million which produces the maximum length sequence. Do note that intermediate numbers might cross the 1 million mark.

The first thing that struck me was the repetitive nature of the problem. Say we are checking the lengths for every number and we start from 1 upwards. So, by the time we get to 13, we would have already calculated the value of 10. If we remember this value, then the value for 13 effectively becomes 3 + value for 10. Thus memoization can be used to speed up the computation.

But if we remember all the values, we will require a very large array as the number greater than 1 million are bound to occur. An another interesting thing struck me. Consider the number 16. It has only 2 predecessors in the sequence, namely 5 and 32. No other number can land on 16 in one step. So, if I know the values for 5 and 32, I need not know the value for 16 anymore. Also note that we shall not miss the largest sequence value by removing keys like this because its predecessors will have a larger sequence length.

Using these two ideas I implemented a recursive solution to give me the answer. Well, I did get the answer but the time taken was large. It took 3845ms to get the answer.

The first modification was to replace the recursive function with an iterative one. This reduced the time taken to just 1907ms. However, the one drawback of moving from a recursive solution to an iterative one was that while in recursive I was able to store the path lengths for intermediate numbers too, in the iterative one I am able to store the results for the starting number only. I suppose if I have a stack of the numbers visited, then I might be able to add their values and consolidate the map so as to remove the unnecessary entries.

At this point, another thing came to my mind. I had used a hash map to remember the already computed values. I remembered Prasun telling me that the jvm allocates a default space to the map, which is as low as 11, if the initial size of the map is not specified. When the number of values being put into the map increases, the map size is readjusted. And since I had not specified any initial size, my map was undergoing all these extra operations. So I went ahead and specified a map of size 1 million. Voila! The time reduced to under 1500ms.

Another couple of observations I made was regarding the size of the map. If I do not optimize the map to contain only the essential entries, then the map is as large as 97000 entries. But with the optimization function that I have used, the size required reduces to 62000. A further modification of calculating the lengths for only odd numbers reduces the map size to just 48500, which is half of the original usage. And since the time invested in periodic optimization of the map contributes to only some 100ms, I think it is a good enough trade off to optimize the entries stored in the map.

All said and done, it is a brute force solution with memoization. I look to better the solution sometime. Below is the code that I have written.

import java.util.HashMap;
import java.util.Map;

import stopwatch.Stopwatch;

public class Problem_14 {
	private static long MAX_NUMBER = 1000000;
	private Map<Long, Integer> m_pathLengths = new HashMap<Long, Integer>((int) (2 * Problem_14.MAX_NUMBER));

	public long getLongestChainStartingNumber() {
		int maxLength = 0;
		long maxLengthStartNumber = -1;

		for (long i = 30001; i < Problem_14.MAX_NUMBER; i += 2) {
			int length = getPathLength(i);
			if (length > maxLength) {
				maxLength = length;
				maxLengthStartNumber = i;
			}
		}
		System.out.println(m_pathLengths.size());

		return maxLengthStartNumber;
	}

	private int getPathLength(Long val) {
		long value = val;
		int pathLength = 0;
		for (; val > 1; pathLength++) {
			if (m_pathLengths.containsKey(val)) {
				pathLength += m_pathLengths.get(val);
				break;
			}
			val = val % 2 == 0 ? val / 2 : 3 * val + 1;
		}
		m_pathLengths.put(value, pathLength);
		optimiseMap(value);

		return pathLength;
	}

	private void optimiseMap(long keyAdded) {
		if (keyAdded % 2 == 1) {
			// odd key added.
			// 5 -> 16, 16 can be reached from only 5 or 32
			// 7 -> 22, 22 can be reached from only 7 or 44
			long keyToBeChecked = 3 * keyAdded + 1;
			if (m_pathLengths.containsKey(2 * keyToBeChecked))
				m_pathLengths.remove(keyToBeChecked);
		} else {
			// even key added.
			// 32 -> 16, 16 can be reached from only 5 or 32
			// 18 -> 9, 9 can be reached from only 18
			long keyToBeChecked = keyAdded / 2;
			if ((keyToBeChecked - 1) % 3 == 0) {
				if (m_pathLengths.containsKey((keyToBeChecked - 1) / 3))
					m_pathLengths.remove(keyToBeChecked);
			} else
				m_pathLengths.remove(keyToBeChecked);
		}
	}

	public static void main(String[] args) {
		Stopwatch stopwatch = new Stopwatch();
		stopwatch.start();
		System.out.println(new Problem_14().getLongestChainStartingNumber());
		stopwatch.stop();
		System.out.println("The reading for operation is: " + stopwatch);
	}
}

Popularity: 8% [?]

Project Euler : Greatest Product of 4 Numbers In A 20×20 Grid

Published on December 17, 2009 in Problems. 0 Comments

This is the 11th problem from Project Euler and I have used brute force to solve it.

Brute force:

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;

public class Problem_11 {
	private static int s_gridSize = 20;

	public int getMaxProduct(int[][] numberGrid) {
		int maxProduct = 0;

		for (int i = 0; i &amp;amp;lt; Problem_11.s_gridSize; i++)
			for (int j = 0; j &amp;amp;lt; Problem_11.s_gridSize; j++) {
				int max = getMax(new int[] { getHorizontalProduct(i, j, numberGrid),
				        getVerticalProdut(i, j, numberGrid), getDiagonalProductA(i, j, numberGrid),
				        getDiagonalProductB(i, j, numberGrid) });
				if (max &amp;amp;gt; maxProduct)
					maxProduct = max;
			}

		return maxProduct;
	}

	private int getHorizontalProduct(int iIndex, int jIndex, int[][] numberGrid) {
		if (iIndex &amp;amp;gt; Problem_11.s_gridSize - 4)
			return 0;
		else
			return numberGrid[iIndex][jIndex] * numberGrid[iIndex + 1][jIndex] * numberGrid[iIndex + 2][jIndex]
			        * numberGrid[iIndex + 3][jIndex];
	}

	private int getVerticalProdut(int iIndex, int jIndex, int[][] numberGrid) {
		if (jIndex &amp;amp;gt; Problem_11.s_gridSize - 4)
			return 0;
		else
			return numberGrid[iIndex][jIndex] * numberGrid[iIndex][jIndex + 1] * numberGrid[iIndex][jIndex + 2]
			        * numberGrid[iIndex][jIndex + 3];
	}

	private int getDiagonalProductA(int iIndex, int jIndex, int[][] numberGrid) {
		if (iIndex &amp;amp;gt; Problem_11.s_gridSize - 4 || jIndex &amp;amp;gt; Problem_11.s_gridSize - 4)
			return 0;
		else
			return numberGrid[iIndex][jIndex] * numberGrid[iIndex + 1][jIndex + 1] * numberGrid[iIndex + 2][jIndex + 2]
			        * numberGrid[iIndex + 3][jIndex + 3];
	}

	private int getDiagonalProductB(int iIndex, int jIndex, int[][] numberGrid) {
		if (iIndex &amp;amp;gt; Problem_11.s_gridSize - 4 || jIndex &amp;amp;lt; 3)
			return 0;
		else
			return numberGrid[iIndex][jIndex] * numberGrid[iIndex + 1][jIndex - 1] * numberGrid[iIndex + 2][jIndex - 2]
			        * numberGrid[iIndex + 3][jIndex - 3];
	}

	private int getMax(int... numbers) {
		int max = numbers[0];
		for (int i = 1; i &amp;amp;lt; numbers.length; i++)
			if (numbers[i] &amp;amp;gt; max)
				max = numbers[i];
		return max;
	}

	public static int[][] getNumbersGrid(String fileName) throws IOException {
		BufferedReader bufferedReader = new BufferedReader(new FileReader(fileName));

		int[][] numberGrid = new int[Problem_11.s_gridSize][];

		for (int i = 0; i &amp;amp;lt; Problem_11.s_gridSize; i++) {
			numberGrid[i] = new int[Problem_11.s_gridSize];
			String[] nums = bufferedReader.readLine().split(&amp;amp;quot; &amp;amp;quot;);
			for (int j = 0; j &amp;amp;lt; Problem_11.s_gridSize; j++)
				numberGrid[i][j] = Integer.parseInt(nums[j]);

		}

		return numberGrid;
	}

	public static void main(String[] args) throws IOException {
		String fileName = &amp;amp;quot;problem_11.in&amp;amp;quot;;
		System.out.println(new Problem_11().getMaxProduct(Problem_11.getNumbersGrid(fileName)));
	}
}

Popularity: 5% [?]

Project Euler : Adding 100 50-Digit Numbers

Published on December 17, 2009 in Problems. 0 Comments

The problem number 13 asked to find the first 1o digits of the sum of 100 50-digit numbers. Well, it was a pretty straight forward task. I think the purpose of this problem was to build an adder to add any large numbers. So I created a new class called BigNumber which stores the numbers as an arraylist of integers.

Here is my code:

public class Problem_13 {
	private static int s_numberOfDataRows = 100;

	public String addNumbers() throws IOException {
		BigNumber[] numbers = readNumbersFromFile();
		return BigNumber.add(50, numbers).toString();
	}

	private BigNumber[] readNumbersFromFile() throws IOException {
		String fileName = "problem_13.in";
		BigNumber[] numbers = new BigNumber[Problem_13.s_numberOfDataRows];

		BufferedReader bufferedReader = new BufferedReader(new FileReader(new File(fileName)));
		for (int i = 0; i < Problem_13.s_numberOfDataRows; i++)
			numbers[i] = new BigNumber(bufferedReader.readLine());

		return numbers;
	}

	public static void main(String[] args) throws IOException {
		System.out.println(new Problem_13().addNumbers());
	}
}

class BigNumber {
	ArrayList<Integer> m_digits;

	public BigNumber(String number) {
		int lengthOfNumber = number.length();
		m_digits = new ArrayList<Integer>(lengthOfNumber);
		for (int i = lengthOfNumber - 1; i >= 0; i--)
			m_digits.add(number.charAt(i) - '0');
	}

	public BigNumber(int sizeOfBigNumber) {
		m_digits = new ArrayList<Integer>(sizeOfBigNumber);
	}

	public int getDigitAtIndex(int index) {
		return index < m_digits.size() ? m_digits.get(index) : 0;
	}

	public void insertDigit(int position, int digit) {
		m_digits.add(position, digit);
	}

	public String toString() {
		int size = m_digits.size();
		StringBuffer number = new StringBuffer(size);
		for (int i = 0; i < size; i++)
			number.insert(0, getDigitAtIndex(i));

		return number.toString();
	}

	public static BigNumber add(int maxLength, BigNumber... numbers) {
		BigNumber sum = new BigNumber(maxLength);

		int carry = 0;
		for (int i = 0; i < maxLength; i++) {
			int partialSum = carry;
			for (BigNumber number : numbers)
				partialSum += number.getDigitAtIndex(i);
			sum.insertDigit(i, partialSum % 10);
			carry = partialSum / 10;
		}

		if (carry != 0)
			sum.insertDigit(maxLength, carry);

		return sum;
	}
}

Popularity: 12% [?]

Project Euler : Fast Factorial Computation

Published on December 16, 2009 in Problems. 0 Comments

The $20^{th}$ problem in Project Euler asked the summation of all the digits in $100!$ . I searched over the net for fast factorial algorithms and came across this site:

Fast Factorial Functions

I implemented the Poor Man’s algorithm to solve the problem. However, I wasn’t able to find out the logic behind the working of the algorithm. Poor Man’s algorithm for factorial returned no good searches. I need to keep looking.

The code given at the above site is in C++. It was a child’s play to convert it into Java. It was mostly copy-paste and remove any C++ specific method to Java one.

Below is the Java code:

public class Problem_20 {
	private long N;

	public String factorial(int n) {
		if (n < 0)
			return "n > 0 required as input";
		if (n < 2)
			return "1";
		DecInteger p = new DecInteger(1);
		DecInteger r = new DecInteger(1);
		N = 1;
		int h = 0, shift = 0, high = 1;
		int log2n = (int) Math.floor(Math.log(n) * 1.4426950408889634);
		while (h != n) {
			shift += h;
			h = n >> log2n--;
			int len = high;
			high = h - 1 | 1;
			len = (high - len) / 2;
			if (len > 0) {
				p = DecInteger.multiply(p, product(len));
				r = DecInteger.multiply(p, r);
			}
		}
		r = DecInteger.multiply(r, DecInteger.pow2(shift));

		return r.toString();
	}

	private DecInteger product(int n) {
		int m = n / 2;
		if (m == 0)
			return new DecInteger(N += 2);
		if (n == 2)
			return new DecInteger((N += 2) * (N += 2));
		return DecInteger.multiply(product(n - m), product(m));
	}

	public static void main(String[] args) {
		int n = 100;
		Problem_20 p = new Problem_20();
		String val = p.factorial(n);
		int sum = 0;
		for (int i = 0; i < val.length(); i++)
			sum += val.charAt(i) - '0';
		System.out.println(sum);
	}
}

class DecInteger {
	private final static long mod = 100000000L;
	private int[] digits;
	private int digitsLength;

	public DecInteger(long value) {
		digits = new int[] { (int) value, (int) (value >> 32) };
		digitsLength = 2;
	}

	private DecInteger(int[] digits, int length) {
		this.digits = digits;
		digitsLength = length;
	}

	public static DecInteger pow2(int e) {
		if (e < 31)
			return new DecInteger((int) Math.pow(2, e));
		return DecInteger.multiply(DecInteger.pow2(e / 2), DecInteger.pow2(e - e / 2));
	}

	public static DecInteger multiply(DecInteger a, DecInteger b) {
		int alen = a.digitsLength, blen = b.digitsLength;
		int clen = alen + blen + 1;
		int[] digits = new int[clen];
		for (int i = 0; i < alen; i++) {
			long temp = 0;
			for (int j = 0; j < blen; j++) {
				temp = temp + a.digits[i] * (long) b.digits[j] + digits[i + j];
				digits[i + j] = (int) (temp % DecInteger.mod);
				temp = temp / DecInteger.mod;
			}
			digits[i + blen] = (int) temp;
		}
		int k = clen - 1;
		while (digits[k] == 0)
			k--;
		return new DecInteger(digits, k + 1);
	}

	public String toString() {
		StringBuffer val = new StringBuffer(digitsLength * 10);
		for (int j = 0; j < digitsLength; j++)
			val.insert(0, digits[j]);
		return val.toString();
	}
}

Popularity: 17% [?]

Project Euler : Sum Of Digits In a^b

Published on December 14, 2009 in Problems. 0 Comments

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));
	}
}