Given a number expressed in base, exponent form (ab) where a is arbitrary big number For example contains 100 digits, We have to write a program to find the last digit in it’s expanded form.
Eg: 45712 has a last digit of 1
Since the range of numbers is huge, it is impossible to expand the number using standard data types like int, and long. We can use library classes to calculate the exponent (Eg. BigInteger in Java), but this is will take a long time to compute the result.
For this problem, we don’t need to expand the result at all!
The trick here is to find the power of last digit in the base. The last digit in the expanded form always depends on the last digit of the base. It is always in the range of [0-9].
What if the exponent is also a big number?
We have to observe that the powers of single digit repeat after if we go on increasing the exponent.
Look at the following table. It gives a fair idea of our approach.
| 1 | 2 | 3 | 4 | |
|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 1 |
| 2 | 2 | 4 | 8 | 6 |
| 3 | 3 | 9 | 7 | 1 |
| 4 | 4 | 6 | 4 | 6 |
| 5 | 5 | 5 | 5 | 5 |
| 6 | 6 | 6 | 6 | 6 |
| 7 | 7 | 9 | 3 | 1 |
| 8 | 8 | 4 | 2 | 6 |
| 9 | 9 | 1 | 9 | 1 |
The the last digit in the power of 2 repeats every multiple of 4. Similarly the last digit in powers of 4 repeats every multiple of 2. and so on.
Based on this observation we can write the following program to calculate the last digit in ab for arbitrary large numbers.