Hello all!
I have a task to code a program that would find the last non-zero digit of the factorial of a given number n where 1<n<10000
so far i got this:

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

int main()
{
int a, xxx;
unsigned long long b=1;
string x;
stringstream buf;
cin>>a;
for(int i=2; i<=a; i++)
{
b=b*i;
while(b%10==0){
b=b/10;
}
}
buf<<b;
buf>>x;cout<<x[x.length()-1];
system("pause");
return 0;
}``````

The problem is that i cannot store the factorials of bigger numbers, and i find using arrays a little too complicated. Any help is greatly appreciated.
Regards, FREEZX

It could be that you've to write your own function (which can handle strings) to multiply two numbers, in that case you can calculate factorials of very big numbers ...

the problem is in handling the big numbers

the problem is in handling the big numbers

If I'm not wrong you mean: The factorials are becoming too big to store in a standard C++ datatype ?

Is that right?

Maybe you should try to implement the following algorithm:

E.g: 6! = 1*2*3*4*5*6
But: 6! = (1/10) * (2/10) * (3/10) * (4/10) * (5/10) * (6/10) *(10^6)

In that case you can already calculate factorials of very high numbers as you can simply do the following:
> 6! = 0.1*0.2*0.3*0.4*0.5*0.6 = 0.00072
> Now you convert this number to a string
> Now you shift your result (in the string) by 6 times (= the number where you're calculating the factorial of) e.g:

``````0.00072 (before you started shifting)
0.0072 (first shift)
0.072
0.72
7.2
72
[U]720[/U] (sixth shift) ==> Now you've found the factorial of 6 !``````

> Now you've your factorial (in a string)

REMARK: If you're working with C-strings you shouldn't forget to reserve enough memory ...

thats what i meant when i said arrays as a string is an array of chars :)..

thats what i meant when i said arrays as a string is an array of chars :)..

A c-string is an array of chars, but this algorithm is also working for C++-strings ...

Actually you only have to find the last non-zero digit of a factorial ...
So you even don't have to calculate the whole factorial ...

As you saw in my previous post you simply could do the following:
6! = 0.1*0.2*0.3*0.4*0.5*0.6*(10^6)
To calculate the factorial of 6 ...

Now you put this into a c-string ... (use the `atof` -command)
If you've don this, you only have to read out the last character of that c-string/char-array, that's the last non-zero digit of the factorial ...

So if you want to find the last non-zero digit of the factorial of 6 you calculate: 0.1*0.2*0.3*0.4*0.5*0.6 = 0.00072

> You use the `atof` -function to convert 0.00072 to a c-string ...
> You read out the last character of the c-string (the subscript of the last character is always returned by `strlen` )

You can also just read out the (n+1) character of the c-string ...
If you have 6! as a string: "0.00072", you notice that the last character is always the number where you took the factorial of plus one (for the decimal point), so you don't need `strlen` ...

Oh, sorry: I was wrong about the use of `atof` as it is to convert a string to a double ...
So you'll have to use for e.g: string streams to convert a number to a string ...

I've found a better algorithm !
Forget about what I said and just write a function which calculates the last digit of a multiplication of two numbers ...

commented: thanks +1
commented: yes +18

xD i never realised it could be this easy... wow the last non-zero digit of a factorial is most significant in finding the factorial of the next factorial.. Thank you! rep for you!

I tried to solve it but somehow my code is not working correctly. the buffer is not doing input and output correctly. here's the code:

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

int main()
{
int a, xxx;
unsigned long long b=1;
string x;
stringstream buf, buff;
cin>>a;
for(int i=2; i<=a; i++)
{
b=b*i;
while(b%10==0){
b=b/10;
}
buff.str(string());
buff<<b;
cout<<buff.str()<<endl;
buff>>x;
b=x[x.length()-1]-48;
}
buf<<b;
buf>>x;
cout<<x[x.length()-1];
system("pause");
return 0;
}``````

I've found a better algorithm !
Forget about what I said and just write a function which calculates the last digit of a multiplication of two numbers ...

Actually you've to do this ...

Thats what im trying to do. i have some problems with the buff stringstream not getting the new value of b

This code will calculate the last digit of a multiplication of two numbers:

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

using namespace std;

int str2int(string s);
string int2str(int i);

int main()
{
int n1, n2, digit;
string s1_dig, s2_dig, s3_dig;

n1 = 25;
n2 = 6;

s1_dig = int2str(n1);
s1_dig = s1_dig[s1_dig.length()-1];

s2_dig = int2str(n2);
s2_dig = s2_dig[s2_dig.length()-1];

s3_dig = int2str(str2int(s1_dig)*str2int(s2_dig));
s3_dig = s3_dig[s3_dig.length()-1];

cout << s3_dig << endl;

return 0;
}

int str2int(string s)
{
stringstream ss;
int i;
ss << s;
ss >> i;
return i;
}

string int2str(int i)
{
stringstream ss;
string s;
ss << i;
ss >> s;
return s;
}``````

NOTE: It might be useful to put the code in the main into an apart function (e.g: f_lastdigit(int n1, int n2) )

cool! i now know how it's done

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.