Project Euler no. 16

Question

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?

I would like to solve the Project Euler problem No. 16. I am trying to save the power of 2's in an array. Suppose 2 ^ 6 = 128. Then

int arr[1000];
arr[0] = 1 // or 8 (In other way also)
arr[1] = 2
arr[2] = 8 // or 1
// and so on....

But now the problem is how to solve this.

I am fetching problem in shifting the digit to next array location. Suppose now,

arr[0] = 8;

In next iteration

arr[0] = 1; and array[1] = 6;

Here arr[0] contains 1 and arr[1] contains 6. Next

arr[0] = 3;
arr[1] = 2;
....
....
//2 ^ 6
arr[0] = 1;
arr[1] = 2;
arr[2] = 8;
...
...
//2 ^ 10
arr[0] = 1;
arr[1] = 0;
arr[2] = 2;
arr[3] = 4;
.....
.....

and so on. Please help me.

Answer 1

{    
auto power=1000;
vector<int> result (1,2); // 
for(auto i =2; i<=power; i++ )
{
    auto carry =0;
    for (auto & elem : result)
    {
        auto mult = elem*2 + carry;
        if (mult > 9)
        {
            elem= mult-10;
            carry=1;
        }
        else
        {
            elem= mult;
            carry=0;
        }
    }
    if(carry)
        result.push_back(carry);

 }

auto sum=accumulate(result.begin(),result.end(),0);
cout<< "Euler 16: sum of the digits of 2^1000 ="<< sum << endl;
}

Answer 2

You can use string in order to find to solution. Here's my code:

#include <bits/stdc++.h>
#define ll long long int
using namespace std;
int main(){
    vector<int> v;
    string s="1";  
    int r,n,res=0;  
    for(int i=0; i<1000; i++){
        r=0,n=0;
        for(int j=s.size()-1; j>=0; j--){
            n=r+(s[j]-'0')*2;
            v.push_back(n%10);
            r=n/10;
        }
        if(n>=10) v.push_back(n/10);
        s="";
        for(int k=v.size()-1; k>=0; k--){
            s+=to_string(v[k]);
        }
        v.clear();
    }
    for(int i=0; i<s.size(); i++){
        res+=(s[i]-'0');
    }
    cout<<res<<'\n';
}

Answer 3

In this problem we can benefit from the computation for previous number. for example to calculate pow(2,1000) we can use digits of pow(2,999), we can store digits of previous number in a queue. Current number can be obtained by multiplying digits of the previous number by 2 one by one.

In the below code above approach has been used:

using namespace std; 
#include<bits/stdc++.h>

int main() {

    queue<int> q;
    q.push(2);
    queue<int> q2;

    for (int i = 2; i <= 1000;i++) {

        int carry = 0;
        while (!q.empty())
        {
            int first = q.front();
            q.pop();
            int digit = (first * 2 + carry) % 10;
            carry = (first*2) / 10;
            q2.push(digit);
        }
        if(carry!=0) {
            q2.push(carry);
        }
        swap(q, q2);
    }

    int sum = 0;
    while(!q.empty()) {
        sum += q.front();
        q.pop();
    }
    cout << sum << endl;
}

Answer 4

here's my java code to problem 16

Answer 5

Here is my Python code:

b = 2**1000
c = str(b)

d = [ ]

for dig in c :

    d.append(int(dig))

e = sum(d)

print e

Answer 6

#include <stdio.h>

#define POWER 1000

int digits[(POWER * 302 + 999)/1000] = {1}; // > log10(2 ** POWER)
int ndigits = 1;

int main(void)
{
    for (int i = 0; i < POWER; i++)
        for (int n = 0, j = 0;; j++)
        {
            n += digits[j] * 2;
            digits[j] = n % 10;
            n /= 10;
            if (j == ndigits - 1)
            {
                if (!n) break;
                ndigits++;
            }
        }

    int sum = 0;
    for (int i = 0; i < ndigits; i++)
        sum += digits[i];

    printf("%d\n", sum);

    return 0;
}

Edit: A possibly faster but more obscure inner block:

            n += digits[j] * 2;
            if (n >= 10)
            {
                digits[j] = n - 10;
                n = 1;
                if (j == ndigits - 1)
                    ndigits++;
            }
            else
            {
                 digits[j] = n;
                 if (j == ndigits - 1)
                     break;
                 n = 0;
            }

Answer 7

Here's my code

#include <iostream>
#include <cstdio>
using namespace std;

int main() {

int a[10000]={0};
int m=1;
int carry=0;
a[0]=1;
long long int sum=0;
for(int i=1;i<=1000;i++)
{
    for(int j=0;j<m;j++)
    {
        int x=a[j]*2+carry;
        a[j]=x%10;
        carry=x/10;
    }
    while(carry!=0)
    {
        a[m++]=carry%10;
        carry/=10;
    }
  }
  for(int i=m-1;i>=0;i--)
   sum+=a[i];
  printf("%lld",sum);
  return 0;
}

Answer 8

    //Finally I did it.


    #include <stdio.h>
#include <stdlib.h>
//2 ^ 1000
int main()
{
   int array[1000] = { 0 };
   array[0] = 1;
   int i, j, cnt, div, carry, temp, sum;
   for(i = 0, cnt = 1; i < 1000; i++)
   {
       div = carry = 0;
       for(j = 0; j < 1000; j++)
       {
           if(carry != 0)
           {
               array[j] = (array[j] * 2) + carry;
               div = array[j] % 10;
               temp = array[j] / 10;
               array[j] = div ;//+ carry;
               carry = temp;
               //array[j] = (array[j] * 2) + 1;
               //carry = 0;
           }
           else
           {
               array[j] = array[j] * 2;
               if (array[j] > 9)
               {
                   div = array[j] % 10;
                   carry = array[j] / 10;
                   array[j] = div;
               }
           }

       }

   }
   sum = temp = 0;
   printf("The value of 2 ^ 1000 is : ");
for(i = 999; i >= 0; i--)
{
    if(array[i] || (temp))
    {
        temp++;
        sum = sum + array[i];
        printf("%d", array[i]);
    }

}
   printf("\nThe sum is : %d \n", sum);
   printf("\nThe number of digits are : %d \n", temp);
    return 0;
}

Answer 9

#include <stdio.h>

void mul2(int *n){
    int c = 0, v;
    while(*n>=0){
        v  = c + *n * 2;
        c  = v / 10;
        *n++ = v % 10;
    }
    if(c) *n++ = c;//1
    *n = -1;//stopper
}

int sum(int *n){
    int sum=0;
    while(*n>=0)
        sum += *n++;
    return sum;
}

int main(void){
    int arr[1000] = {1, -1};//need 302 + 1, -1 is stoper
    int i;
    for(i=0;i<1000;i++)
        mul2(arr);
    printf("%d\n", sum(arr));
    return 0;
}

Answer 10

You should go over each digit, starting with the least significant one, double it and add the carry from the previous one, store the result modulo 10 as the new digit value and if the result is more than 9, set the carry to 1 otherwise set it to 0 (or just perform integer division of the result by 10):

carry = 0
for i = 0 to MAX_DIGITS-1:
   tmp = 2 * digits[i] + carry
   digits[i] = tmp % 10
   carry = tmp / 10

(this is pseudocode - translate it to C for your own use)

---

Just as a side note, computing 2^1000 is extremly easy in binary - it is just 1 followed by 1000 0. Converting the result to decimal representation is a bit tricky but an efficient binary to BCD conversion methods exist. But I would still recommend that you use the GNU MP library instead. It only takes 6 lines to compute 2^1000 using GNU MP (the #define line and all whitespace lines are not counted):

#include <gmp.h>

#define MAX_DIGITS 302

mpz_t bignum;
char str[MAX_DIGITS+2];

mpz_init2(bignum, 1001);
mpz_ui_pow_ui(bignum, 2, 1000);  // set the integer object to 2^1000
mpz_get_str(str, 10, bignum);    // convert to base 10

Note that 2^1000 is 1001 binary digits and about 302 (equal to 1001*log(2)) decimal digits. Add two characters for a possible sign character and a NULL terminator character as requried by mpz_get_str().

Now you only have to go over the resulting digits in str, convert them to integers and sum them all up.