Find the sum of digits of 2^1000

[sanalsprasad]

Hi.
I am trying to do this question http://projecteuler.net/index.php?section=problems&id=16

Can anyone tell me how to approach this problem in detail?
Thank You.

[kbw]

An example is given with the question. Why not use that as the approach?

[sanalsprasad]

2^15 = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26.
well, i dont think there will be any data type which will hold the value of 2^1000
i calculated the value using google and found that
2^ 1000 = 1.07150861e301

How will i store this 302-digit number ?

[kbw]

You don't store it, you sum the digits.

[Albatross]

Okay.

EDIT: If you want to store it, create your own data type. Make a structure that contains multiple integers for parts of the integer, but raised to a different power of ten.

http://cplusplus.com/doc/tutorial/structures/

If you want to sum its digits without storing, that's a different story, and a different calculation altogether. Make a special request if you want me to give a very generic solution to that problem.

-Albatross

[jsmith]

Any solution involving actually performing 1000 big int multiplications will not
meet project euler's solution criteria.

[jsmith]

Well, I sorta take that back.

My solution executed in 38 milliseconds.

It is quite hard-wired though to multiply by 2.

(EDIT: without optimization; with optimization = 4 milliseconds)

[sanalsprasad]

@Albatross
will u tell me how would i do that by giving a simple example on how to compute it, divide the number into parts and store it ?
please also tell me how to compute the sum without knowing the exact value.

[jsmith]

You'll need the exact value in order to compute the sum.

Just keep an array of integers where each element stores one digit of the result. Eg, to represent "128" in this
way, you'd have an array of 3 integers:

int array[3] = { 1, 2, 8 };

Now write a function that multiplies the number stored in the array by 2 (multiply it in place).

[m4ster r0shi]

I did it too! ^^ Took me 15 ms to calculate 2^1000 and sum the digits and less than 1 ms to calculate 256^125 (which is the same) and find the sum :P This isn't an assignment right? I mean I can't imagine his teacher saying: "I want you to solve the 20 first problems from project euler within the next week!". So why don't we give him some more help?

I'll go with jsmith's method but I'll use a vector of ints to store the digits coz during the multiplication you may need to add more digits (or you could just use an array of 350 digits (ints), more than you'll need for this problem in any step of the solution...). Consider the following:

x=(abc)₁₀

That is x=100*a + 10*b + c

Now, 2*x=100*2*a + 10*2*b + 2*c=1000*d' + 100*a' + 10*b' +c'
(note that we may have an extra digit here)

You can calculate the new values for the digits like this:

c'=2*c
b'=2*b+c'/10
a'=2*a+b'/10
d'=a'/10

c'%=10
b'%=10
a'%=10

Note that you can easily modify this to cover for multiplication with any given k (instead of just 2). But then you'll have to be a little careful coz you may have more than one new digits at a time... If you do this using a vector put the least significant digit in the beginning of the vector so that you can simply push_back new digits when necessary.

HINT: The result is LEET increased a bit! LOL, that made a rhyme, neat! LOL, that also made a rhyme! (Ok, I'll just stop here...)

[sanalsprasad]

i finally figured it out.....all i had to do was remember how to multiply by 2.......

#include "stdafx.h"
#include<iostream>
#include<vector>
using namespace std;


int main()
{
	vector<int> digits ;
	digits.push_back( 1 );
	for( int i=1; i<=1000; i++)
	{
		int carryover = 0;
		for ( vector<int>::iterator iter = digits.begin(); iter != digits.end(); iter++ )
		{
			*iter = *iter * 2 + carryover;
			if ( *iter > 9 && (iter+1) != digits.end() )
			{
				*iter -= 10;
				carryover = 1;
			}
			else if ( *iter > 9 && (iter+1) == digits.end())
			{
				*iter -= 10;
				digits.push_back(1);
				break;
			}
			else if ( *iter <= 9 )
				carryover = 0;
		}
	}

	int sum = 0;

	for ( vector<int>::iterator iter = digits.begin(); iter != digits.end(); iter++ )
		sum += *iter;
	
	cout << sum;

	cin.get();
	return 0;
}

Please tell me if there is anyother way to solve it......