Just like the solution to problem 13 the answer to problem 16 of Project Euler has become trivial with .NET 4.0. And since I am lazy I intend to exploit the tools I am given. The problem description reads
215 = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26.
What is the sum of the digits of the number 21000?
If there didn’t exist a BigInteger class in .NET, then we would have needed to implement a way of storing the large result, which would need 1000 bits of storage, or around the size of 32 integers.
Solution
However, with the class that can hold arbitrarily large in integers the task is trivial, and I decided to solve it in the following way
int result = 0;
BigInteger number = BigInteger.Pow(2, 1000);
while (number > 0) {
result += (int) (number % 10);
number /= 10;
}
I have chosen an implementation where I slice of the last digit in a while loop with the modulo operator. We could have chosen to convert it to a string, split it and convert it back. This just seemed more in line with the Project Euler spirit.
The result of the code is
The sum og digits of 2^1000 is: 1366 Solution took 0 ms
Wrapping up
Intentionally this was a very short blog post, since I didn’t have much to say. As usually the source code is available for download here.
Hello Everyone,
I have a simple code in C# which does not make use of BigInteger..
I have not commented about what I have done in code so that you can find out whats going on in the code.. The code is very simple..
using System; class mainclass { public static void Main(string[] args) { int sum = 0; int[] arr = new int[400]; //Just a wild guess about the number of digits that 2 ^ 1000 will have arr[0] = 2; int carry = 0; for (int j = 1; j < 1000; j++) { for (int i = 0; i < arr.Length; i++) { int tempno = arr[i] * 2; if (tempno > 9) { arr[i] = (tempno % 10) + carry; carry = 1; } else { arr[i] = tempno + carry; carry = 0; } } } for (int i = 0; i < arr.Length; i++) { sum += arr[i]; Console.Write(arr[i]); } Console.WriteLine(); Console.WriteLine("Sum of Digits = " + sum); } }Hi Amey
Thanks for the comment and the alternative solution. I always love to see and hear from other people.
I like your solution, since it doesn’t use anything special, so it would be implementable in most traditional languages. On the other hand I have no problems using the tools that the chosen language provides me for solving the problem at hand.
I have made a solution that is somewhat similar, but where I store 14 digits in each array entry. That uses less memory, but you need to chop up each number in the end, so I am not sure whether or not it is better performance wise.
If I should make any comments on the code, I would add the carry in line 19 instead. I know it won’t make any problems, but it seems easier to understand for me.
/Kristian
Hi Kristian,
I have been reading your blog here for a few weeks now and I am so glad I found it. I love your solutions to the problems, here is my version (not as cool as yours).
BigInteger
.Pow(2, 1000)
.ToString()
.Aggregate(0,
(total, next) => total + (int)Char.GetNumericValue(next))
Hi Mark
Thanks for the compliment and thanks for sharing your code. I am not very strong with LINQ, so I always enjoy when people are sharing their LINQ solutions with me. That gives me a little to pull from whenever I am trying.
/Kristian