Euler Problem from Hackerrank, code complete but not correct

[Detslibli]

Hello everyone, Im in my 2nd course for programming and learning c++, for a final I was tasked with solving a euler problem from hackerrank. I have code done but when submitted, it only passes 1 of the 10 cases in hackerrank. I need pass them all or atleast most of them. Future thanks for any help.

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int main() 
{
    int tests, squared, sumofDigits;
    unsigned int digit = 0;
    int base = 2;
    int array[3];

    cin >> tests;

    if (1 <= tests && tests <= 100)
    {
        for (int i = 0; i < tests; i++)
        {  
            cin >> digit;
            if (1 <= digit && digit <= 10000)
            {
                int square = pow(base,digit);
                squared = square;

                for (int i = 2; i >= 0; i--) 
                {
                    array[i] = squared % 10;
                    squared /= 10;
                }
            
                sumofDigits = array[0] + array[1] + array[2];
                cout << sumofDigits << endl;  
            }
        }
    }
        return 0;
}

[helios]

(2^10000)^2 = 2^20000, which is a number with over 6000 decimal digits, and most computers aren't able to handle directly integers with more than 20 digits, so you'll need to figure out some way to add the three least significant decimal digits that doesn't involve putting that number into an int.

[againtry]

3980276840337966592354307206191202453704772780492425938713
42686565238635974930057042676009749975595510836461137504912702831
40037693531914362175347041582702598121528242689349822482661597770
75955394669610195886997267722797319413151981827872640348528212001
64566127930390710398182979935327718016873784821349516406114982916
69186736187537002454587214079382727748256282419243923780158869781
41685203386500909096975359665250327570494302864594829773573735980
20450589927318365663076719136934132593126761906696003770385305284
57033111969100152658434772201238638188177942554921085169645825394
35785576990721546396556307938839419613789718468411138041887302589
03839103669626086974468150655710480841592465655211805257863007811
67688883955501753673175811344865675251415860144405164515466551438
84316190423961067167557623387281834613698546489239729044275561588
21823778729193111453445844216979095435045778144571378954652122396
06161514764254025074585722889399987549162501494601383934089132606
09339010362499992386378275777746666448097340338616194203639364651
78730919233673114244563915058438996625834112132967998495576249320
46287174777701216554388715625585835878485233506057488187655202568
57048237680787108189518607413794292421108556449739774204138103735
14584504006896392675854997866870818564207239083874324953871276375
71610150657515320574736396374074986751468261975677553450700687148
58878124029277382275766352841742469885407859752400204812668530761
27172228024330561550120182008777598230542033702463408316671120886
16926093400680579986459863631117978777673860899234606306309965964
82796638781740747871792371697529570464045845253013841533583440559
08219695854852185210739761460551596658211013159915409566145426809
73755041757822846583583089029449753546311208153767266405689162434
57793115245600199843154561421262828984867283450047678734997526834
71409587367450593302392307908004590644754012537113320493601682133
70931822264748908053164401532139115738717823215412682800776031371
68722422096142009675221804757161999736894677140104046739614541464
66045855232217196687665143147612199151921277432309700460321430381
53338524587743133053347947615233936450343632291966563104232874046
36125658425604119470201740065078933962761038344362331409150253910
14386119201176462659556388343058600326710618903683746516577021214
27693328917902105995692594971795604085797916591417097005621286993
35935892686261519966765943708008850930482306871528032132547355947
41799076039453057272319884322341883241036382617598401889439130301
87697549868173617421571128705344701371159600457480356270138824682
25103915224190613206637409213217543441667448995881606492918235359
83386025904942040724581017615968429577015808090360968544059204594
20006930461241736639877683153226559622471575030179220772560793253
45436937587722620103873604355676352327183434206796930573600040736
79493008945813961012439574397373178636054628207647520675194420244
27103634372931885843087146197886696477236205729057732608066446312
96575902498597485441013338420927136530966560662668274460791455901
96644643417403723220085696202719321533233027169599734928971588850
34841500007003402702529818310414834398029766314897158660790377171
78806831754364455858106105468820735715561623246593513103265608044
48974229349743425637164834242799991427145050899469511954834774847
17236069356843768914739945567209077368678251105429118517238191700
88899576453113399509930447797836071405937665080179359925813578583
06525303783231752425242008347844867988333025417249944092118578113
68740315816270707515400605341637407576516266853312707860531656282
63371936062425352906832244236604622224086803004987141496072655504
41220738075941633988435051594487256802874182264814425923111193188
28063201312780289788960533878308953274087720230412249819362545476
83437755354988728210999816204970708104891374571068925732484987342
43717184800822956334469415666818858073218653977954309023182851723
24652204279240146138200160192050128443932521408421073640063088492
99422729829436137081230113552609155458310431602435235993720062261
50289664982113944898886610710824955096724626895416484521819026132
17764059869165803598628537635503371909456808312221934572206361360
97791583380843753314312765275484825662100713477445412928718761347
64249704859840950276227627328897424208932988115108907187647698491
81437563961431317809252867800737004587174821842178639619728421320
90226237627346308360068641924146052372489832890069052689884751975
99781524158913583701325199090352274252608342971303907669363045656
23218397875585306400401089503083492198860135520118115887725480779
80586351277084455920645195631150947492766066975595293328072214140
21024905241788974917755034700510432039890197393691722911126889174
39431212725479314162497583042909799770553178190824208392206876902
73551292126172441306402899947774130266240131573299483335863779551
03195844817163822484232700763859290253400376515701986753596890075
81854448547578578003184357906575409509997094050464021285080999705
11289765638808863924107663214499875296904632621828942723027491545
35447233331028841215215533602398281107050696017507827602761547816
32474329793817720418376582111781886995979503184820132243605310377
89935413847798572623114658957540855383719690409224209369150766535
00310175006188572019017358300979056992161958286882575984331858170
85730336126989131279436924489654032319245167883066818045505928974
35806407360762335619358881095258458031259123889655241668198559770
61399043499229843517930169118036812460794615667808961600389778306
54032484928650151529279939130451099729812822825800615601738987808
62727899933214163492059216356969637035589713911231748773537575367
74013315034956942784403824181551741629180658414081905650333672638
98341678638809502616949660519974969159579883594718977782276519876
79496997781066838629891030960065058652710035663461913824060116739
58404009194852110016915222433459641787170917872140367871023596464
05164794738858057077446230434789620167619719552142878231360858371
43992380922083629332113029428064801755894023879765310804369068568
34377344137698180789562645974374155400497754843905032231188252125
802180353577510519869570675234892321663406309376

She's right! FWIW that's what 2^20,000 looks like. Somebody can do the digit count but all we need know is that C++ doesn't handle integers anywhere near that size. Python does! But that doesn't help if C++ is mandatory.

So it is fair to say if you need to handle numbers that big, let alone square numbers on the way, you need to re-think your program.

A number is an array of digits, or even a <vector> etc of them and that's probably where you need to focus. Remember also if you take two numbers in the array and process them (+, -, * or divide) you will have the last digit plus a carryover.

Of course, int square = pow(base,digit); isn't the square of base, unless digit is always 2. Besides, pow() returns a floating value not an integer. See: http://www.cplusplus.com/reference/cmath/pow/

Maybe if you copy the question, or the Euler problem number being addressed a more definitive answer can be given.

(For instance
Euler Problem 16 is:

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?
)

[againtry]

And then there is this one that appears to be vaguely related even though n = 100. FWIW this one doesn't require arrays.

Euler Problem 6 is:
The sum of the squares of the first ten natural numbers is,
12 + 22 + ... + 102 = 385

The square of the sum of the first ten natural numbers is,
(1 + 2 + ... + 10)2 = 552 = 3025

Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025 − 385 = 2640.

Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

[Detslibli]

Thank you guys for your replies, I see, so int is not the datatype to which to handle the square of the bases. Float should be used I assume. Also yes, I forgot to include the Euler problem.

https://www.hackerrank.com/contests/projecteuler/challenges/euler016/problem?isFullScreen=true

[helios]

No, floating point types will also not help you.

[dhayden]

Float won't handle all those digits either. [Edit: see dutch's comment below] You need to come up with an algorithm that doesn't require storing all the digits. Hint: When multiplying AxB, if you only want to know the least significant 3 digits then you only have to multiply the 3 least significant digits of A and B.

[dutch]

The question is "What is the sum of the digits of the number 2**N for N from 1 to 10000?"
It doesn't mention the "least significant 3 digits" that I can see.

[lastchance]

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

void doubleIt( vector<int> &number )
{
   int N = number.size();
   for ( int &i : number ) i += i;          // double digits

   for ( int i = 0; i < N - 1; i++ )        // do the "carries" (maximum of 1 for doubling)
   {
      if ( number[i] > 9 )
      {
         number[i] -= 10;
         number[i+1]++;
      }
   }
   if ( number[N-1] > 9 )
   {
      number[N-1] -= 10;
      number.push_back( 1 );
   }
}


void writeIt( const vector<int> &number )
{
   int N = number.size();
   for ( int i = N - 1; i >= 0; i-- ) cout << number[i];
}


int sumIt( const vector<int> &number )
{
   int sum = 0;
   for ( int i : number ) sum += i;
   return sum;
}


int main()
{
/*
   vector<int> A = { 1 };
   int M = 20;
   for ( int i = 1; i <= M; i++ )         // First M powers of 2 as a check
   {
      doubleIt( A );
      cout << "2^" << i << " = ";   writeIt( A );   cout << '\n';
   }
*/


// Business
   int N = 10000;
   vector<int> B = { 1 };
   vector<int> SUMS( 1 + N );   SUMS[0] = 1;

   for ( int i = 1; i <= N; i++ )
   {
      doubleIt( B );
      SUMS[i] = sumIt( B );
   }

   cout << "2^" << N << " = ";   writeIt( B );   cout << '\n';
   cout << "The sum of the digits in 2^" << N << " is " << SUMS[N] << '\n';
}

[againtry]

const int LIMIT = 400;
    int n[LIMIT] = {0};
    int temp, carryover = 0, remainder = 0, sum = 0;
    
    n[0] = 1;
    
    for (int k = 0; k < 1000; k++)
    {
        for (int i = 0; i < LIMIT; i++)
        {
            temp = 2 * n[i] + carryover;
            
            carryover = temp/10;
            remainder = temp % 10;
            
            n[i] = remainder;
        }
    }

Or use dreaded <vector>'s and then there is automatic sizing of the 'array' and no need for LIMIT.

Note also by squaring it takes only 10 steps to get to 2^1024. Then divide by 2 24(?) times to get back to 2^1000

[dutch]

I certainly didn't mean to suggest it wasn't easy to solve, just that it didn't involve only the last 3 digits.

So there's your homework done for you!
By losers, of course!
You're welcome!

[againtry]

2^1000 =
10715086071862673209484250490600018105614048117055
33607443750388370351051124936122493198378815695858
12759467291755314682518714528569231404359845775746
98574803934567774824230985421074605062371141877954
18215304647498358194126739876755916554394607706291
45711964776865421676604298316526243868372056680693
76

[helios]

The question is "What is the sum of the digits of the number 2**N for N from 1 to 10000?"
It doesn't mention the "least significant 3 digits" that I can see.

I don't know, I haven't seen a link to the actual question yet.

[dhayden]

I don't know, I haven't seen a link to the actual question yet.

It's in post #5.

Another approach is to form the binary number (1 followed by N zeros and then convert to BCD using this algorithm: https://my.eng.utah.edu/~nmcdonal/Tutorials/BCDTutorial/BCDConversion.html. I'm not sure if that's easier or harder than doing the math in decimal from the start.