blah~

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 digit
 43:                 {
 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
This entry was posted in Uncategorized. Bookmark the permalink.

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