Welcome to week 16 of my Project Euler series.
Problem 16:
What is the sum of the digits of the number 21000?
Details:
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?
Code:
//What is the sum of the digits of the number 21000?
class Problem0016
{
static void Main(string[] args)
{
const int numberBase = 10; // The base that we are going to be using (2, 10, and 16 are the most common)
const int power = 1000; // The power that will be used.
int arraySize = power / (numberBase * 3); // The size of the array can be approximated to the power / base * 3
int[] bigNumber = new int[arraySize + 1];
bigNumber[0] = 2; // Our big number will start as 2.
for (int i = 2; i <= power; i++)
{
DoubleNumber(bigNumber);
}
var numberAsString = NumberToString(bigNumber);
Console.WriteLine("The sum of digits of 2^" + power + " is " + SumTheDigits(numberAsString));
Console.Read();
}
private static void DoubleNumber(int[] n)
{
int carry = 0;
for (int i = 0; i < n.Length; i++)
{
n[i] <<= 1;
n[i] += carry;
if (n[i] >= 1000000000)
{
carry = 1;
n[i] -= 1000000000;
}
else
{
carry = 0;
}
}
}
private static String NumberToString(int[] n)
{
int i = n.Length;
while (i > 0 && n[--i] == 0)
;
String ret = "" + n[i--];
while (i >= 0)
{
ret += String.Format("{0:000000000}", n[i--]);
}
return ret;
}
private static int SumTheDigits(string text)
{
int returnValue = 0;
foreach (var number in text)
returnValue += int.Parse(number.ToString());
return returnValue;
}
}
Solution:
This one requires a little more digging into what was learned long long ago in math. It also involves thinking about more than just "int" or "long" to get it figured out. We have once again a number that is going to be well beyond the scale of what is available to us for numeric data types. That hasn't stood in our way before and it won't this time either. We are going to take a, once again, different approach to things. This time we are going to work with the number as if it were an array. The trick is that we are going to work with an array of 9 digit numbers (numbers under 1 billion).
As we all might or might not know a signed int has a value right around +- 2 billion. That would be a bit awkward to work with if we are going to be using the various elements of the array for continuous calculations. We can however put a cap on the number that we use where ever we want to. If we wanted to work with over sized arrays, we could just as easily have worked with the 3 digit numbers (under 1 thousand). For simplicity though, we went with the largest number that .NET data types would allow.
If you check out the DoubleNumber method you will get a better idea of what I mean. I am doing binary addition to each number in the array. If there is something that goes over our 9 digit cap that we self imposed, then it is used as a carry over into the next element of the array. At the end we get a truly impressive sized number to work with. That is also why we have to transfer it into a string in order to add all the digits. I suppose technically it would have worked to just pace through the array and do it that way, but I had implemented the method to turn it into a string in order to check my output during testing and solving of it, so I just left it in and used it here.
This brings me to another good point. I decided to start breaking this code up into methods for two reasons. First off, I was having some issues when I was trouble shooting the code and wanted to get things a little more spread out and easier to work with. Once I was able to get the return value I wanted and expected from a method then I knew that that chunk of code worked. I could safely move on and let the method enjoy a long and happy life. That actually ties directly into the second reason; Readability. To really prove this point, I will put some extra code onto my Google code repository. I could have very easily squeezed all this code into the main method and not had to worry about making sure my method calls were right and my return values were what I wanted. The problem is that I would have then had a very hard task ahead of me when I started trying to isolate code for debugging purposes. It would have been possible (and shorter) but the readability and future maintenance would have suffered. I like to consider the rule of thumb that a method should fit comfortably on your screen. Of course buying a bigger screen is not the solution if it doesn't but rather trying to take out some code that both, logically fits together, and is capable of standing alone without causing issues. Since it is a rule of thumb it is not necessary to do, but rather nice if possible. It allows you to focus one line of thought on the screen at a time.
Until next time...
Enjoy!
2 grid, there are 6 routes (without backtracking) to the bottom right corner.
in C#. Simple right? Once you have a grasp of C# and binomial coefficients it really is. The only real question that was left over was, what are n and k in this example? In reading some interesting articles about path finding, I found people using this equation to solve the number of paths from one side of a 2d map to the other. k was the length of on of the sides and n was the number of steps from one side to the other. Plop those in the proper place in your equation and you have yourself an answer.