3

I am trying to solve the Project Euler Problem #16: https://projecteuler.net/problem=16. It requires me to sum up every digits from the result of 2^1000.

I iterate through the string (converted from double type) by treating the string as an array. However when I try to convert string digit back to int, I always got error.

I tried with stoi, It prompts me "no matching function for call to 'atoi'". I also tried with stringstream for conversion, it still did not work.

Please see my following code:

#include <iostream>
#include <complex> // pow
#include <string> // to_string C++ 11

const double NUM = pow(2, 1000);

int main(int argc, char const *argv[]) {
    int sum = 0;
    //printf("%.0f\n", NUM); // Remove decimal digits
    auto str = std::to_string(NUM);
    std::string str_trim = str.substr(0, str.length()-7);
    std::cout << str_trim << std::endl; // 2^1000 in string

    for (int i = 0; i <= str_trim.length(); i++) {
        std::cout << str_trim[i] << std::endl;
        sum = sum + str_trim[i];
        std::cout << sum << std::endl;
    }
    return 0;
}

Any idea to solve this problem? Thank you.

Improve this question
4
  • Remove the extra information. What is the main issue? You can't convert a number written as a string to an int, right? Commented Jun 26, 2015 at 6:57
  • 2
    Anyway, your approach to the question is wrong. Since you need to add the digits, you need to be able to figure out the exact value of 2^1000. As far as I remember, even a double won't be able to store 2^1000. And more importantly, you will lose a lot of information in form of digits while storing it as a double, and so you can't add the digits for the correct answer. Commented Jun 26, 2015 at 6:59
  • The code "std::cout << str_trim << std::endl;" seems print out the answer (over 300 digits). I think it should be OK to work with double. Commented Jun 26, 2015 at 7:01
  • For 2^1000 the approach, amazingly enough, works fine. The reason is that ieee754 double format will lose precision by considering missing bits to be zeros... and in 2^1000 all bits (except MSB) are zeros. Commented Jun 26, 2015 at 7:06

3 Answers 3

Reset to default
3

For a pure coincidence this approach will work fine on most compilers for 2^1000 because the rounding done by IEEE754 double format (the most common format for floating point numbers in C++) will drop bits by considering them to be zeros (and in 2^1000 those bits are indeed zeros).

To sum up the digit you can just iterate over the chars and execute

total += s[i] - '0';

using the fact that in C++ chars are indeed small integers.

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

Smartypants, plus one! (So I can recover some dignity: C++ does not insist on IEEE754, so your approach will only work on some compilers.)
@Bathsheba: true... with "some" defined as 99.975% :-D ... and by the way I had to try with Python to be sure that int(pow(2.,1000))==2**1000 before posting. Never thought about this before (i solved that EP problem the "standard" way).
0

If you need to convert std::string to int use std::stoi. C++ also has a few other functions for other types: std::stoi, std::stol, std::stoll, std::stoul, std::stoull, std::stof, std::stod, std::stold

Still no C++ type can hold 2^1000 so you can't use standard types and standard functions for such values.

Improve this answer

1 Comment

Actually, for a lucky coincidence, a double-precision number on most C++ compilers can hold 2^1000 exactly (the reason is that the dropped bits will be considered to be zeros, and they're indeed zeros in 2^1000).
0

Even if you manage to extract the digits from the NUM your answer will be incorrect:

const double NUM = pow(2, 1000);

cannot be relied upon to store the number exactly.

An alternative way of solving this problem is to evaluate 2 to the 1000th power in binary (the result is simple: it is 1 followed by 1,000 zeros). Your problem is then reduced to converting that back to base 10 and summing the digits; perhaps even doing that part simultaneously. But you will not be able to use any of the built-in types to represent that number. That is what makes this problem interesting.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.