Given two numbers n and m, where n and m can be as large as 10^9 and n>=m. Find the last digit that will be in the value of n! / m!.
Examples :
Input : 59 57 Output : 2 Input : 10 0 Output : 0 Input : 57 31 Output : 0
Example 1 : 59! / 57! = 59*58 = 3422, last digit is 2 Example 2 : 10!/0! = 10*9*8*…*1 = 3628800, last digit is 0. Approach : Since the number can be as large as 10^9, we cannot calculate it in naive way. The intuition here is that we are interested in finding the last digit, and last digit of number depends on last digit of all multiples. Say for example : 12*11*10, the last digit depends on the multiples of last digit of given number, that is 2*1*0 = 0. hence last digit will be 0. we can extend this idea further. Since we want to calculate n!/m! where n>=m, n!/m! will be in the form of n*(n-1)*(n-2)*…*(m+1). Since the last digit of the product depends on last digit of multiples,let’s say last digit of the given sequence be x1,x2,…,xn. answer will be Last_digit(x1*x2*..xn). Now if any of x[i] =0, answer will be 0 and we do not have to consider it further. This way in constant time we can get the value of n!/m! in constant time and constant space.
Implementation :
#include<bits/stdc++.h>
using namespace std;
int getlast(int n,int m)
{
/// if both numbers are same they will cancel out each other and answer will be 1.
if(n==m) return 1;
int difference = n-m;
/// if the difference is greater than 9, we will get a 0 as last digit in some multiple of integer hence answer will be 0
if(difference>=9) return 0;
/// if the last digit of n is 0, answer will be 0
if(n%10==0) return 0;
/// else we will find the product of all the last digits and answer will be last digit of the product.
/// the maximum we can iterate is from 9 to 1, 9*8*7*6*5*4*3*1, since difference needs to be less or equal to 8
int ans=1;
int last=n%10;
for(int i=1;i<=difference;++i){
ans = ans * last;
last--;
}
int lastdigit = ans % 10;
return lastdigit;
}
int main()
{
int n=59 , m=57;
int Lastdigit = getlast(n,m);
cout <<"Last digit in n!/m! is : " << Lastdigit<<endl;
return 0;
}
