Home > Programming > Project Euler: Problem 16: Find the sum of all the digits in 2 power 1000

Project Euler: Problem 16: Find the sum of all the digits in 2 power 1000


This problem is simple and straight forward. I’ve used a character buffer to store the powers of 2 for each iteration starting from 1 to 1000.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char *strrev(char *str)
{
      char *p1, *p2;

      if (! str || ! *str)
            return str;
      for (p1 = str, p2 = str + strlen(str) - 1; p2 > p1; ++p1, --p2)
      {
            *p1 ^= *p2;
            *p2 ^= *p1;
            *p1 ^= *p2;
      }
      return str;
}
int main(void)
{
    char *digits = (char *)malloc(sizeof(char) * 2000);
    memset(digits, 0, 2000);
    digits[0] = '1';
    unsigned int carry = 0;
    int i, j;
    for (i = 0; i < 1000; i++) {
        carry = 0;
        for (j = 0; j < strlen(digits); j++) {
            int m = (digits[j] - '0') * 2 + carry;
            carry = (m / 10) % 10;
            digits[j] = (m % 10) + '0';
        }
        if (carry)
            digits[j] = carry + '0';
    }
    strrev(digits);
    printf("2 power 1000 is: %s\n", digits);
    carry = 0;
    for (int i = 0; i < strlen(digits); i++)
        carry += (digits[i] - '0');
    printf("Answer: %d\n", carry);
}

2 power 1000 is:

10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668069376

Answer: 1366

real 0m0.085s
user 0m0.015s
sys 0m0.062s

One interesting thing to notice here is that the above same code can be written in python with in a single line using comprehensions as follows. 🙂


sum([int(n) for n in str(2**1000)])

>>> sum([int(n) for n in str(2**1000)])
1366

Advertisements
Categories: Programming Tags: , ,
  1. August 3, 2015 at 9:56 pm

    I’m so glad to have stumbled upon your site, it has some pretty awesome stuff. On the subject of Project Euler, especially this problem, I would like to point you to my mathematical/programming blog:

    http://www.chaitanyavarier.com

    As I have published a post about a Java Big Arbitrary Precision Calculator I recently developed, which might be of interest to you. I will also be posting my own solutions to many PE problems that I’ve solved.

  1. No trackbacks yet.

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: