Project Euler problem 16~

`1: class Program`

2: {3: static void Main(string[] args)4: {`5: var sw = new Stopwatch();`

6:`7: Console.WriteLine("The sum of the digits of the number 2^(1000)");`

8: sw.Start();9: var sum1 = test3(1000);10: sw.Stop();11: Console.WriteLine(string.Format("plain arithmetic brute force way(tick:{0}): {1}", sw.ElapsedTicks, sum1));12:13: sw.Reset();14:`15: Console.WriteLine("Press any key to exit");`

16: Console.ReadKey();17: }18:`19: /// <summary>`

`20: /// 2*1 = 2, 2*2 = 4 = (2*1)*2 = (2*1) + (2*1)`

`21: /// so 2^(n+1) = (2^n) + (2^n)`

`22: /// using the same way of adding big numbers from question 13`

`23: /// so basically we add the number in the array(int[] map) to itself for each power iteration`

`24: /// the size of array is 1000, assume that each addition would advance one decimal`

`25: /// (which is a pretty crude estimate)`

`26: /// but the code use the count variable to control number of loop for inner for`

`27: /// so 2^3 = 8 = 2^2 + 2^2 = just need to loop 1 time`

`28: /// 2^4 = 16 = 2^3 + 2^3 = [1][6]..... advance count by 1, so now on loop 2 times at least`

`29: /// </summary>`

`30: /// <param name="power"></param>`

`31: /// <returns></returns>`

32: static int test3(int power)33: {34: var map = new int[power];35: map[0] = 2;36: var count = 1;37: var sum = 0;38: var rem = 0;39: var carry = 0;40: for (int i = 1; i < power; i++)41: {42: for (int j = 0; j < count; j++) // so for each digit43: {44: sum = map[j] * 2 + carry;45: rem = sum % 10;46: map[j] = rem;47: carry = (sum - rem) / 10;`48: if (j == count - 1 && carry > 0)`

49: {50: map[j + 1] += carry;51: carry = 0;52: count++;`53: break;`

54: }55: }56: }`57: return map.Sum();`

58: }59: }

Advertisements