## Tuesday, August 30, 2016

### Find Last Digit Of a^b for Large Numbers - GeeksforGeeks

Find Last Digit Of a^b for Large Numbers - GeeksforGeeks
You are given two integer numbers , the base a (number of digits d, such that 1 <= d <= 1000) and the index b (0 <= b <= 922*10^15). You have to find the last digit of a^b.

This is simple mathematical problem. It is recommended to refer this article for some basic concept of solving such problems. Here both numbers are very large so we have to store them as a string.
In the given table, we can see that maximum length for cycle repetition is 4.
`// Function to find b % a`
`int` `Modulo(``int` `a, ``char` `b[])`
`{`
`    ``// Initialize result`
`    ``int` `mod = 0;`

`    ``// calculating mod of b with a to make`
`    ``// b like 0 <= b < a`
`    ``for` `(``int` `i=0; i<``strlen``(b); i++)`
`        ``mod = (mod*10 + b[i] - ``'0'``)%a;`

`    ``return` `mod; ``// return modulo`
`}`

`// function to find last digit of a^b`
`int` `LastDigit(``char` `a[], ``char` `b[])`
`{`
`    ``int` `len_a = ``strlen``(a), len_b = ``strlen``(b);`

`    ``// if a and b both are 0`
`    ``if` `(len_a==1 && len_b==1 && b[0]==``'0'` `&& a[0]==``'0'``)`
`        ``return` `1;`

`    ``// if exponent is 0`
`    ``if` `(len_b==1 && b[0]==``'0'` `)`
`        ``return` `1;`

`    ``// if base is 0`
`    ``if` `(len_a==1 && a[0]==``'0'``)`
`        ``return` `0;`

`    ``// if exponent is divisible by 4 that means last`
`    ``// digit will be pow(a, 4) % 10.`
`    ``// if exponent is not divisible by 4 that means last`
`    ``// digit will be pow(a, b%4) % 10`
`    ``int` `exp` `= (Modulo(4,b)==0)? 4 : Modulo(4, b);`

`    ``// Find last digit in 'a' and compute its exponent`
`    ``int` `res = ``pow``(a[len_a - 1] - ``'0'``, ``exp``);`

`    ``// Return last digit of result`
`    ``return` `res % 10;`
`}`