Project Euler – Problem 16


What is the sum of the digits of the number 2^1000?

Problem:
2^(15) = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26.

What is the sum of the digits of the number 2^(1000)?

My Solution:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Globalization;

namespace Euler
{
    class Problem16 : IProblemBase
    {

        //2^(15) = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26.

        //What is the sum of the digits of the number 2^(1000)?

        public Problem16()
        {
        }

        //http://weblogs.sqlteam.com/mladenp/archive/2006/03/19/9350.aspx
        public string Reverse(string x)
        {
            char[] charArray = new char[x.Length];
            int len = x.Length - 1;
            for (int i = 0; i <= len; i++)
                charArray[i] = x[len - i];
            return new string(charArray);
        }

        public int CharToInt(char c)
        {
            return Int32.Parse(c.ToString());
        }

        public string GetAnswer()
        {
            int result = 0;
            int limit = 1000;
            int pow = 2;
            int remainder = 1;

            List<int> bigInt = new List<int>();

            for (int i = 1; i <= limit; i++)
            {
                int nextIntIteration = remainder * pow;

                char[] c = Reverse(nextIntIteration.ToString()).ToCharArray();

                if (bigInt.Count == 1 && nextIntIteration > 10)//double digits for the first time
                {
                    bigInt[0] = CharToInt(c[0]);
                    bigInt.Add(CharToInt(c[1]));
                }
                else if (bigInt.Count == 1 && nextIntIteration < 10)//still in single digits
                {
                    bigInt[0] = CharToInt(c[0]);
                }
                else if (bigInt.Count <= 0 && nextIntIteration < 10)//single digits first the first time
                {
                    bigInt.Add(CharToInt(c[0]));
                }
                else
                {
                    //replace 0 index of array
                    int new0Index = CharToInt(c[0]);

                    //set array 0 index always
                    bigInt[0] = new0Index;

                    int carryBits = 0;
                    if (c.Length > 1)
                    {
                        carryBits = CharToInt(c[1]);
                    }

                    int charSumRunningTotal = 0;
                    //the list can grow so we get init count
                    int loopCnt = bigInt.Count;
                    //need to loop through remainding char array and double + remainder
                    for (int k = 0; k < loopCnt; k++)
                    {
                        //ignore first pass
                        if (k != 0)
                        {
                            charSumRunningTotal = (pow * bigInt[k]) + carryBits;
                            if (charSumRunningTotal >= 10)
                            {
                                //have to move the array
                                char[] cInner = Reverse(charSumRunningTotal.ToString()).ToCharArray();

                                bigInt[k] = CharToInt(cInner[0]);
                                if (k == bigInt.Count - 1)
                                {
                                    bigInt.Add(CharToInt(cInner[1]));
                                }

                                carryBits = CharToInt(cInner[1]);
                                cInner = null;

                            }
                            else
                            {
                                bigInt[k] = charSumRunningTotal;
                                carryBits = 0;
                            }
                        }

                    }

                }

                remainder = bigInt[0];
                c = null;

            }
            bigInt[0] = remainder;

            //add them up
            foreach (int k in bigInt)
            {
                result = result + k;
            }

            return result.ToString();

        }

    }
}
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: