factoral challenge

[olzi]

hi, im stuck on a math/programming challenge.

the challenge

"Given the first few factorials:

1! = 1
2! = 2 x 1 = 2
3! = 3 x 2 x 1 = 6
4! = 4 x 3 x 2 x 1 = 24
What is the sum of the first 15 factorials, NOT INCLUDING 0!? "

i have wrote a small c++ program

#include <cstdlib>
#include <iostream>

using namespace std;

int main()
{
int total;
long sum=1;
int counter=1;


for (int i = 1; i < 16; i++)
{
    sum= sum*counter;
    counter++;
    cout << i << "!Factoral" << "=" << sum << endl;
}



    system("PAUSE");
    return EXIT_SUCCESS;
}

now the code loops and gives multiplies the 'sum' by the counter, now i cant decide if it is asking me to sum all the values i.e 1! + 2! + 3! = 9 etc or just the sum of the 15th factoral = 1x2x3x4x...15 = 1307674368000 ( acording to the calculator ) but my program spits out

1!Factoral=1
2!Factoral=2
3!Factoral=6
4!Factoral=24
5!Factoral=120
6!Factoral=720
7!Factoral=5040
8!Factoral=40320
9!Factoral=362880
10!Factoral=3628800
11!Factoral=39916800
12!Factoral=479001600
13!Factoral=1932053504
14!Factoral=1278945280
15!Factoral=2004310016

so my question is in two parts (a) would i add up the sum each time it loops and store it in an array ie total = sum[1]+sum[2] +sum[n](1+2+6+24...n) n how would i program that?
(b) why is my program giving a different result for the 15th factoral compared to the trusty calc.exe?

thanks in advance

[Gaminic]

b) Because your variable type is too small. By the looks of it, you're already losing data once you hit fac(13). Check here:
http://msdn.microsoft.com/en-us/library/s3f49ktz(VS.80).aspx

a) Why would you? This version is more elegant. However, if you really want to:

int a[16]; // Prepare array
a[0] = 1; // Initialize first value as 1 

Then replace your line 15 with:

sum[i] = sum[i-1] * counter;

That way, each sub-result will be saved and used for the next step.

Also, small tip: You don't need the 'counter' variable. In every iteration, it will be the same as 'i', so might as well dump it and use 'i' instead!

[olzi]

@Gaminic thanks for the quick reply but i am getting a wierd output now.

1!Factoral=0x22fef0
2!Factoral=0x22fef0
3!Factoral=0x22fef0
4!Factoral=0x22fef0
5!Factoral=0x22fef0
6!Factoral=0x22fef0
7!Factoral=0x22fef0
8!Factoral=0x22fef0
9!Factoral=0x22fef0
10!Factoral=0x22fef0
11!Factoral=0x22fef0
12!Factoral=0x22fef0
13!Factoral=0x22fef0
14!Factoral=0x22fef0
15!Factoral=0x22fef0

if i change the *counter to *i it will do the same thing so thank you for that :D
and can you explain why = sum[i-1]*counter ?
sum[i] = sum[i-1] * counter;
why is it [i-1] when surley you want to +1 to move allong the array? sorry programming isnt my strong point, although it should be having a degree in computer games technology and its a programming heavy course lol

thanks

[Gaminic]

You have to change your cout line. You should now print sum[i], not sum. (Sum is, afaik, a pointer to the first element of the array, i.e. useless as output. If that is chinese to you, ignore it for now).

The sum line is read as this:
"Assign the current sum (sum[i]) the value of the previous sum (sum[i-1]) multiplied by the current counter number (i)". The 'i-1' doesn't mean "move back" or "move ahead"; it means "access the previous number in the array". Thus, if i = 6, sum[i-1] will access the fifth element in the array (i.e. the value of "5!") and calculate the result, then save it in sum[i].

[olzi]

ahh thank you :) makes a bit more sense,n i got why my output was showing the address of the pointer 'duh' silly me.

i have ran it in debug and put a watch on 'sum' and it looks like it works and i changed the 'cout' to 'sum[i]' still the problem is that the array is storing an 'int' and im getting the same values as i was in my first attempt :\

[Gaminic]

I'm not sure which types are supported, but try one of the bigger types found on the webpage I linked (e.g. long long). One of them might exist. Thing is, factorials increase in value drastically at each "+1" so no matter the variable type, you'll always hit the ceiling of what a variable can store pretty soon.

[olzi]

thanks :D thats got me the right answers for the !15 factoral now. its showing '1307674368000 ' when i used the unsigned long long for sum[16];

my only problem now is i will need to sum each factoral value, eg sum[0] + sum[2]+.. sum[15]
i have added this loop :

for (int i = 1; i < 16; i++)
{
   total = sum[i] + sum[i-1];
   
    cout << "total ="  << total << endl;

}

i dont think that this is the right way as its not summing what i need it to.

[olzi]

i did this insread:

{
   total = sum[1] + sum[2] + sum[3] + sum[4] +sum[5] + sum[6] + sum[7] + sum[8] + sum[9] +sum[10] + sum[11] + sum[12] + sum[13] + sum[14] + sum[15];
   
    cout << "total ="  << total << endl;

}

and it gave me the right number to the challenge, but there must be a cleaner more efficient way of doing that sum

[Gaminic]

Of course there is: loop over the array!

unsigned long long total = 0;
for (int i = 0; i < 16; ++i) { // Or int it = 1 if you want to skip the first
  total += sum[i];
}

You can simply combine it with the previous loop as well by adding the total in that loop. Or, if you wish, you can keep the "total" in sum[]: just change the "sum[i] = sum[i-1]*i;" line to "sum[i] += sum[i-1]*i;". You won't have the separates any more though, so it might be worth keeping them and using the separate total.

[olzi]

thanks alot :D this has helped me out loads.

1!Factoral=1
2!Factoral=2
3!Factoral=6
4!Factoral=24
5!Factoral=120
6!Factoral=720
7!Factoral=5040
8!Factoral=40320
9!Factoral=362880
10!Factoral=3628800
11!Factoral=39916800
12!Factoral=479001600
13!Factoral=6227020800
14!Factoral=87178291200
15!Factoral=1307674368000
total =1
total =3
total =9
total =33
total =153
total =873
total =5913
total =46233
total =409113
total =4037913
total =43954713
total =522956313
total =6749977113
total =93928268313
total =1401602636313

i get this output now, this makes me happy :D