C++

Forum

 
Project Euler #13

BryanTriana (18)
I am having trouble trying to solve problem 13 in project Euler. The problem asks me to add 100 numbers that are 50 digits long, my take on the solution was to insert the numbers into a string and then operate them every 50 digits. I dont know how to store the sum of these numbers but I read somewhere that I can deal with them as doubles and then use std::setprecision() to know the first 10 digits for the answer.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
 

#include <iostream>
#include <string>
#include <iomanip>
#include <cstdlib>


int main()
{
    
    double p;
    double r=0;
    std::string x;
    std::string n="37107287533902102798797998220837590246510135740250";
    n+="46376937677490009712648124896970078050417018260538";
    n+="74324986199524741059474233309513058123726617309629";
    n+="91942213363574161572522430563301811072406154908250";
    n+="23067588207539346171171980310421047513778063246676";
    n+="89261670696623633820136378418383684178734361726757";
    n+="28112879812849979408065481931592621691275889832738";
    n+="44274228917432520321923589422876796487670272189318";
    n+="47451445736001306439091167216856844588711603153276";
    n+="70386486105843025439939619828917593665686757934951";
    n+="62176457141856560629502157223196586755079324193331";
    n+="64906352462741904929101432445813822663347944758178";
    n+="92575867718337217661963751590579239728245598838407";
    n+="58203565325359399008402633568948830189458628227828";
    n+="80181199384826282014278194139940567587151170094390";
    n+="35398664372827112653829987240784473053190104293586";
    n+="86515506006295864861532075273371959191420517255829";
    n+="71693888707715466499115593487603532921714970056938";
    n+="54370070576826684624621495650076471787294438377604";
    n+="53282654108756828443191190634694037855217779295145";
    n+="36123272525000296071075082563815656710885258350721";
    n+="45876576172410976447339110607218265236877223636045";
    n+="17423706905851860660448207621209813287860733969412";
    n+="81142660418086830619328460811191061556940512689692";
    n+="51934325451728388641918047049293215058642563049483";
    n+="62467221648435076201727918039944693004732956340691";
    n+="15732444386908125794514089057706229429197107928209";
    n+="55037687525678773091862540744969844508330393682126";
    n+="18336384825330154686196124348767681297534375946515";
    n+="80386287592878490201521685554828717201219257766954";
    n+="78182833757993103614740356856449095527097864797581";
    n+="16726320100436897842553539920931837441497806860984";
    n+="48403098129077791799088218795327364475675590848030";
    n+="87086987551392711854517078544161852424320693150332";
    n+="59959406895756536782107074926966537676326235447210";
    n+="69793950679652694742597709739166693763042633987085";
    n+="41052684708299085211399427365734116182760315001271";
    n+="65378607361501080857009149939512557028198746004375";
    n+="35829035317434717326932123578154982629742552737307";
    n+="94953759765105305946966067683156574377167401875275";
    n+="88902802571733229619176668713819931811048770190271";
    n+="25267680276078003013678680992525463401061632866526";
    n+="36270218540497705585629946580636237993140746255962";
    n+="24074486908231174977792365466257246923322810917141";
    n+="91430288197103288597806669760892938638285025333403";
    n+="34413065578016127815921815005561868836468420090470";
    n+="23053081172816430487623791969842487255036638784583";
    n+="11487696932154902810424020138335124462181441773470";
    n+="63783299490636259666498587618221225225512486764533";
    n+="67720186971698544312419572409913959008952310058822";
    n+="95548255300263520781532296796249481641953868218774";
    n+="76085327132285723110424803456124867697064507995236";
    n+="37774242535411291684276865538926205024910326572967";
    n+="23701913275725675285653248258265463092207058596522";
    n+="29798860272258331913126375147341994889534765745501";
    n+="18495701454879288984856827726077713721403798879715";
    n+="38298203783031473527721580348144513491373226651381";
    n+="34829543829199918180278916522431027392251122869539";
    n+="40957953066405232632538044100059654939159879593635";
    n+="29746152185502371307642255121183693803580388584903";
    n+="41698116222072977186158236678424689157993532961922";
    n+="62467957194401269043877107275048102390895523597457";
    n+="23189706772547915061505504953922979530901129967519";
    n+="86188088225875314529584099251203829009407770775672";
    n+="11306739708304724483816533873502340845647058077308";
    n+="82959174767140363198008187129011875491310547126581";
    n+="97623331044818386269515456334926366572897563400500";
    n+="42846280183517070527831839425882145521227251250327";
    n+="55121603546981200581762165212827652751691296897789";
    n+="32238195734329339946437501907836945765883352399886";
    n+="75506164965184775180738168837861091527357929701337";
    n+="62177842752192623401942399639168044983993173312731";
    n+="32924185707147349566916674687634660915035914677504";
    n+="99518671430235219628894890102423325116913619626622";
    n+="73267460800591547471830798392868535206946944540724";
    n+="76841822524674417161514036427982273348055556214818";
    n+="97142617910342598647204516893989422179826088076852";
    n+="87783646182799346313767754307809363333018982642090";
    n+="10848802521674670883215120185883543223812876952786";
    n+="71329612474782464538636993009049310363619763878039";
    n+="62184073572399794223406235393808339651327408011116";
    n+="66627891981488087797941876876144230030984490851411";
    n+="60661826293682836764744779239180335110989069790714";
    n+="85786944089552990653640447425576083659976645795096";
    n+="66024396409905389607120198219976047599490197230297";
    n+="64913982680032973156037120041377903785566085089252";
    n+="16730939319872750275468906903707539413042652315011";
    n+="94809377245048795150954100921645863754710598436791";
    n+="78639167021187492431995700641917969777599028300699";
    n+="15368713711936614952811305876380278410754449733078";
    n+="40789923115535562561142322423255033685442488917353";
    n+="44889911501440648020369068063960672322193204149535";
    n+="41503128880339536053299340368006977710650566631954";
    n+="81234880673210146739058568557934581403627822703280";
    n+="82616570773948327592232845941706525094512325230608";
    n+="22918802058777319719839450180888072429661980811197";
    n+="77158542502016545090413245809786882778948721859617";
    n+="72107838435069186155435662884062257473692284509516";
    n+="20849603980134001723930671666823555245252804609722";
    n+="53503534226472524250874054075591789781264330331690";
  

    for(int i=0; i<n.length(); i=i+50)
    {
        for(int j=0; j<50; j++)
        {
            x=n[i+j];
            
        }
        p=std::atof(x.c_str());
        r=p+r;
        x.clear();
        
    }
  
    std::cout << r<< std::endl;
    
}


I know the code is pretty messy and bad, but I want someone to help me follow a path to solve this problem by using strings.
closed account (48T7M4Gy)
Strings are the hard way to solve this problem. In fact += concatenates the strings and does not add them arithmetically.

Store each number as an array of (100 x) 50 integers and add up each column. It is the same process as if you were solving the problem with pen and paper.
BryanTriana (18)
I tried a solution with a 100 number array and marked numbers as doubles, the answer isnt precise enough though.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
 
#include <iostream>
#include <string>
#include <iomanip>
#include <cstdlib>


int main()
{
    double sum=0;
    double nDig[100]=
    {
        .46376937677490009712648124896970078050417018260538,
        .74324986199524741059474233309513058123726617309629,
        .91942213363574161572522430563301811072406154908250,
        .23067588207539346171171980310421047513778063246676,
        .89261670696623633820136378418383684178734361726757,
        .28112879812849979408065481931592621691275889832738,
        .44274228917432520321923589422876796487670272189318,
        .47451445736001306439091167216856844588711603153276,
        .70386486105843025439939619828917593665686757934951,
        .62176457141856560629502157223196586755079324193331,
        .64906352462741904929101432445813822663347944758178,
        .92575867718337217661963751590579239728245598838407,
        .58203565325359399008402633568948830189458628227828,
        .80181199384826282014278194139940567587151170094390,
        .35398664372827112653829987240784473053190104293586,
        .86515506006295864861532075273371959191420517255829,
        .71693888707715466499115593487603532921714970056938,
        .54370070576826684624621495650076471787294438377604,
        .53282654108756828443191190634694037855217779295145,
        .36123272525000296071075082563815656710885258350721,
        .45876576172410976447339110607218265236877223636045,
        .17423706905851860660448207621209813287860733969412,
        .81142660418086830619328460811191061556940512689692,
        .51934325451728388641918047049293215058642563049483,
        .62467221648435076201727918039944693004732956340691,
        .15732444386908125794514089057706229429197107928209,
        .55037687525678773091862540744969844508330393682126,
        .18336384825330154686196124348767681297534375946515,
        .80386287592878490201521685554828717201219257766954,
        .78182833757993103614740356856449095527097864797581,
        .16726320100436897842553539920931837441497806860984,
        .48403098129077791799088218795327364475675590848030,
        .87086987551392711854517078544161852424320693150332,
        .59959406895756536782107074926966537676326235447210,
        .69793950679652694742597709739166693763042633987085,
        .41052684708299085211399427365734116182760315001271,
        .65378607361501080857009149939512557028198746004375,
        .35829035317434717326932123578154982629742552737307,
        .94953759765105305946966067683156574377167401875275,
        .88902802571733229619176668713819931811048770190271,
        .25267680276078003013678680992525463401061632866526,
        .36270218540497705585629946580636237993140746255962,
        .24074486908231174977792365466257246923322810917141,
        .91430288197103288597806669760892938638285025333403,
        .34413065578016127815921815005561868836468420090470,
        .23053081172816430487623791969842487255036638784583,
        .11487696932154902810424020138335124462181441773470,
        .63783299490636259666498587618221225225512486764533,
        .67720186971698544312419572409913959008952310058822,
        .95548255300263520781532296796249481641953868218774,
        .76085327132285723110424803456124867697064507995236,
        .37774242535411291684276865538926205024910326572967,
        .23701913275725675285653248258265463092207058596522,
        .29798860272258331913126375147341994889534765745501,
        .18495701454879288984856827726077713721403798879715,
        .38298203783031473527721580348144513491373226651381,
        .34829543829199918180278916522431027392251122869539,
        .40957953066405232632538044100059654939159879593635,
        .29746152185502371307642255121183693803580388584903,
        .41698116222072977186158236678424689157993532961922,
        .62467957194401269043877107275048102390895523597457,
        .23189706772547915061505504953922979530901129967519,
        .86188088225875314529584099251203829009407770775672,
        .11306739708304724483816533873502340845647058077308,
        .82959174767140363198008187129011875491310547126581,
        .97623331044818386269515456334926366572897563400500,
        .42846280183517070527831839425882145521227251250327,
        .55121603546981200581762165212827652751691296897789,
        .32238195734329339946437501907836945765883352399886,
        .75506164965184775180738168837861091527357929701337,
        .62177842752192623401942399639168044983993173312731,
        .32924185707147349566916674687634660915035914677504,
        .99518671430235219628894890102423325116913619626622,
        .73267460800591547471830798392868535206946944540724,
        .76841822524674417161514036427982273348055556214818,
        .97142617910342598647204516893989422179826088076852,
        .87783646182799346313767754307809363333018982642090,
        .10848802521674670883215120185883543223812876952786,
        .71329612474782464538636993009049310363619763878039,
        .62184073572399794223406235393808339651327408011116,
        .66627891981488087797941876876144230030984490851411,
        .60661826293682836764744779239180335110989069790714,
        .85786944089552990653640447425576083659976645795096,
        .66024396409905389607120198219976047599490197230297,
        .94809377245048795150954100921645863754710598436791,
        .78639167021187492431995700641917969777599028300699,
        .15368713711936614952811305876380278410754449733078,
        .40789923115535562561142322423255033685442488917353,
        .44889911501440648020369068063960672322193204149535,
        .41503128880339536053299340368006977710650566631954,
        .81234880673210146739058568557934581403627822703280,
        .82616570773948327592232845941706525094512325230608,
        .22918802058777319719839450180888072429661980811197,
        .77158542502016545090413245809786882778948721859617,
        .72107838435069186155435662884062257473692284509516,
        .20849603980134001723930671666823555245252804609722,
        .53503534226472524250874054075591789781264330331690,
    };
    for(int i=1; i<100; i++)
    {
        sum+=nDig[i];
    }
  
    std::cout << std::setprecision(50)<< sum << std::endl;
}
closed account (48T7M4Gy)
Nope. Project Euler is cruel. [][]
newbieg (764)
Kemort is right, this is not the only one that is going to have numbers that are too large even for the long type. The solution I came up with involved setting the numbers to a string and add them together by subtracting the char '0' from each character in the string...

(the char '9' - char '0' = the int 9)

then write the function to add them together while keeping in mind how you were taught addition in elementary school; Cary the tens into the next point over in the string and repeat.
Last edited on
Bdanielz (506)
why not use gmp? https://gmplib.org/
or just use a different language like python?
closed account (48T7M4Gy)
- gmp is a possibility but I reckon it over-complicates the problem if you aren't familiar with its use. But, it's your call.
- there are solutions using python and the big integer capabilities it has
- you can use chars as newbieg mentions or int's in a 2d [][] array
ne555 (10692)
> to know the first 10 digits for the answer
that's your hint. You don't need the exact answer, but an approximation.
The numbers have 50 digits, ¿how much do you think that it would affect you the digit 39th?
Topic archived. No new replies allowed.