Taste of New Languages!!!!!!!

yesterday i code something in Python , after spending some time with it i realize that it made job of programmer quite easy, though Python , perl are scripting languages but very powerful. To handle very long numbers in c/c++ is not an easy task even simple arithmetic of huge number which we do using string is not very easy , it need a close observation and long code but in python it took only 10-12 lines.

While working on a problem i normally check the time taken by best solution , strangely people achieved unbelievable small time, i always amazed by seeing this, what data structure they use , what algorithm they use. After seeing that i always tell me that i have a loooooooooong way to go :)

Factorial !!!!!!!!!!!!

Today i saw a problem which was asked often in technical round of good companies.
Problem : Finding the first non zero digit in the factorial of a number ( for 5! = 120 first non zero digit is 2 ).
Solution : If number is such that its factorial is within the range of even long long then we can use any brute force method like removing digit one by one till we don't get first non zero digit ( though it wont be efficient ).

Here is better solution , i am not claiming it is best , if any one know better please comment it.
We can easily calculate number of zero in the factorial of a number by dividing the number first by 5 then 5 ^ 2 then 5 ^ 3 .......and adding result till 5^i < number.

Let we get that number has n number of zero then we are sure that the number has at least n number of 2 and n number of 5. What we have to do is to just remove n number of 2 and 5 from given number and keep track of last digit , till we get the answer.
here is the working code
int main ()
{
int Num2, Num5;
int Ldigit = 1, tmp;
int Num, NumZero = 0, i;
scanf ( " %d", &Num );
for ( i = 1; ;i++ )
{
tmp = pow ( 5, i );
if ( tmp > Num )
break;
NumZero += Num / tmp;
}
Num2 = Num5 = NumZero;
for ( i = 2; i <= Num; i++ )
{
tmp = i;

while ( !(tmp % 2) && (Num2>0) )
{
tmp /= 2;
Num2--;
}
while ( !(tmp % 5) && (Num5>0) )
{
tmp /= 5;
Num5--;
}

Ldigit *= tmp;
Ldigit %= 10;
}
printf ( " Last Digt = %d\n", Ldigit );
return 0;
}

Integer Overflow

Yesterday i was working on a problem where we have to check a number is whether prime or not , for that i gone through two famous prime testing algorithm , but i was getting wrong answer , i was trying hard but nothing worked , then i searched on internet , where i found very interesting thing.

It is well known that when we have to find the value of a raise to power n , we can calculate it in O ( log n ) time , we can apply same logic when we have to get a * b, what ever we did to n same thing we do to b here. This was the culprit as when i was calculating a * b it was going beyond integer range ( Actually we apply this logic when we have to found modulo of a * b otherwise it is of no use because it will grow beyond longest integer value ).

But above logic won't work if 2 * a goes beyond longest integer range, java provide us with facility to create our own custom integer .