Puzzles, Maths and Algorithms: Finding First Non-Zero Digit of N Factorial
Find the first non-zero digit of N!. Assume N! to be extremely large.
Solution:
If we assume that the product doesnt contain either of 2's and 5's, then finding last digit is trivial. Simple multiply the result with next number and take its mod 10. The problem is complicated as 2's and 5's lead to trailing 0's. So the first step is to remove 2's and 5's. Then solve the problem. The cancel 5's with 2's and multiply back the left over 2's.
For Ex. 7! = 1 * 2 * 3 * 4 * 5 * 6 * 7. We extract 2's and 5's so the product is 1 * 3 * 3 * 7. The trailing digit is 3. We have extracted four 2's and one 5. So we get 3 extra 2's. So multiply to 3 we get 4 as the answer. To check 7! = 5040
Related: [LeetCode] Factorial Trailing Zeroes
Read full article from Puzzles, Maths and Algorithms: Finding First Non-Zero Digit of N Factorial
Find the first non-zero digit of N!. Assume N! to be extremely large.
Solution:
If we assume that the product doesnt contain either of 2's and 5's, then finding last digit is trivial. Simple multiply the result with next number and take its mod 10. The problem is complicated as 2's and 5's lead to trailing 0's. So the first step is to remove 2's and 5's. Then solve the problem. The cancel 5's with 2's and multiply back the left over 2's.
For Ex. 7! = 1 * 2 * 3 * 4 * 5 * 6 * 7. We extract 2's and 5's so the product is 1 * 3 * 3 * 7. The trailing digit is 3. We have extracted four 2's and one 5. So we get 3 extra 2's. So multiply to 3 we get 4 as the answer. To check 7! = 5040
d = 1 n2 = 1for i = 3 to n j = i while j%10 == 0 //remove trailing zeros j /= 10 while j%2 == 0 //count of 2's j /= 2 n2 += 1 while j%5 == 0 //cancel a 5 with a 2 j /= 5 n2 -= 1 d = (d * j) % 10 d = (d * 2^n2) % 10 //multiply remaining 2's to d return dhttps://comeoncodeon.wordpress.com/2009/06/20/lastnon-zero-digit-of-factorial/
Approach 2
This is the most popular technique and quite handy too. We know that n! = 1 x 2 x 3 …x (n-1) x n
or n! = (2^a2)(3^a3)(5^a5)(7^a7)…
or n! = (2^a2)(5^a5)(3^a3)(7^a7)…
This is the most popular technique and quite handy too. We know that n! = 1 x 2 x 3 …x (n-1) x n
or n! = (2^a2)(3^a3)(5^a5)(7^a7)…
or n! = (2^a2)(5^a5)(3^a3)(7^a7)…
Now we know that the number of zeroes in n1 is equal to a5. So n! divided by 10^a5 will be equal to factorial without trailing digits. Lets call this n! without trailing zeroes as (n!)’ .So,
(n!)’ = (2^(a2-a5))(3^a3)(7^a7)…
(n!)’ = (2^(a2-a5))(3^a3)(7^a7)…
Let L(k) denote the least significant non-zero decimal digit of the integer k. So from above we can infer that
L(n!) = L((n!)’) = L[(2^(a2-a5))(3^a3)(7^a7)…]
= L[(3^a3)(7^a7)…]*L[(2^(a2-a5))]
L(n!) = L((n!)’) = L[(2^(a2-a5))(3^a3)(7^a7)…]
= L[(3^a3)(7^a7)…]*L[(2^(a2-a5))]
Related: [LeetCode] Factorial Trailing Zeroes
Read full article from Puzzles, Maths and Algorithms: Finding First Non-Zero Digit of N Factorial