Output not as expected: Project Euler Problem #13

general
,
1

Here’s the code that I wrote for Problem #13 from Project Euler:

#include <iostream>
#include <string>
#include <sstream>
using namespace std;

char const* n2c (int number)
{
    stringstream strs;
    strs << number;
    string temp_str = strs.str();
    char const* pchar = temp_str.c_str();
    return pchar;
}

int main()
{
	string str[100];
	for (int i = 0; i < 100; i++)
	{
		cin >> str[i];
	}
	
	int carry = 0;
	string res = string();
	
	for (int i = 49; i >= 0; i--)
	{
		int count = 0;
		for (int j = 0; j < 100; j++)
		{
			count = count + (str[j][i] - '0');
		}
		res.append(n2c((carry + count) % 10));
		carry = (carry + count)/10;
	}
	string g = string();
	g.append(n2c(carry));
	g.append(res);
	cout << res;
}

The output is not as expected. Any idea why??

2

Actually, the part where you’re appending the ‘res’ is inappropriate. As you see, your loop runs starting from the last column(rightmost) towards the first column(leftmost). Therefore, you first calculate last digit, then second last and so on …

Now, you are appending the res as you go from right to left. This acts like reversing the actual string of calculated digits, which will give wrong answer when appended to the final carry!

So, you should store each calculated digit in ‘some string’ from right to left(e.g. take str[0]) as you go and then finally after all digits and end carry is calculated, you should append this ‘some string’ into the ‘end carry’ string.

Hope this helps !

3

Alright! But even after that, the length of the final res string is lesser than 50. This should not have been the case as length should increase after summation. Any idea what can b the possible bug?

4

I don’t know for sure … but when you declared res, the string was supposed to be empty(but wasn’t). There’s gotta be something about setting of eof bit due to which some of the first few digits didn’t successfully append into res, therefore, length of res became less than 50.

Try reading this, it may explain the above phenomenon

5

Alright can you refer me to some place where I can read up on stringstream? Actually I just copy pasted the stringstream part from somewhere and made it a function without thinking of it implications. If there is a problem with stringstream, should I change my approach?

6

Although, your approach is fine, but you should change return type of function n2c to ‘string’ and return temp_str(Reason : [append][2] function simply takes string argument). This will work for sure!

For stringstream, here’s a link from [cplusplus.com][1].
[1]:http://www.cplusplus.com/reference/sstream/stringstream/?kw=stringstream
[2]:http://www.cplusplus.com/reference/string/string/append/

7

This is how your final code should look like :

#include <iostream>
#include <string>
#include <sstream>

using namespace std;

string n2c (int number)
{
    stringstream strs;
    strs << number;
    string temp_str = strs.str();
//    char const* pchar = temp_str.c_str();
    return temp_str;
}

int main()
{
    string str[100];
    for (int i = 0; i < 100; i++)
    {
	cin >> str[i];
    }
	    int carry = 0;
    string res = string();
	for (int i = 49; i >= 0; i--)
    {
	int count = 0;
	for (int j = 0; j < 100; j++)
	{
	    count = count + (str[j][i] - '0');
	}
	res.append(n2c((carry + count) % 10));
	carry = (carry + count)/10;
    }
	res = string( res.rbegin(), res.rend() );
    //cout<<endl<<res;

    string g = string();
    g.append(n2c(carry));
    g.append(res);
	cout<<endl<<g;
	}