How to find the last non-zero digit K!?

Question

Algorithms

Programming challenge. Help decide.
Masha makes up a sequence where the last non-zero digit K! is in K place. Help her fill in the blanks.
Input:
The first and only line contains the number K (0 ≤ K ≤ 10 ⁵ )
Output: The
last non-zero digit K!
Example: entered 5, output 2.

Answer 1

ideone

<?php

function normalize($num)
{
  while ($num % 10 == 0)
  {
    $num = intdiv($num, 10);
  }
  
  return ($num % 100);
}

$k = 50; //  k! = 30414093201713378043612608166064768844377641568960512000000000000
$result = 1;

for ($i = 2; $i <= $k; $i++)
{
  $result = normalize($result * $i);
}

echo $result % 10; //  2

Answer 2

You can quickly, in log (k), calculate how many zeros there are in k!
To do this, what is the degree of 2 and 5 and take the minimum.
A simple p will go into k! to the power of floor(k/p) + floor(k/p^2) + floor(l/p^3)...
Can this be done easily recursively PowerInFactorial(n, p) = n >= p ? n/p + PowerInFactorial(n/p) : 0;
Now you know how many zeros are in the factorial. If you remove them all, then the task becomes quite simple - to find the last digit. This can be done simply by doing all calculations modulo 10.
That is, multiply all the numbers from 2 to k, beforehand reducing the twos and fives as much as necessary.

twos = fives = min(PowerInFactorial(k, 2), PowerInFactorial(k, 5));
ans = 1;
for ( i = 2; i <= k; i++) {
  j = i;
  while (j % 2 == 0 && twos > 0) {
    j/=2;
    twos--;
  }
  // same for fives
  ...
  ...
  ans = (ans*j)%10;
}

As a result, the solution is O(k), because the nested loops will be filled in total as many times as there are zeros in k!, and according to the formula above, they are less than O(k).