PROBLEM LINK:
Author: Varun Singh
DIFFICULTY:
EASY
PREREQUISITES:
Elementary Number Theory
PROBLEM:
Given two integers b and e, find the last digit of b^e.
QUICK EXPLANATION:
Every digit 0 through 9 has a pattern of 4 digits when raised to an exponential power. Store them in a 2D array, mod the exponent by 4 and look the result up in the 2D array for all queries in constant time.
EXPLANATION:
Each digit from 0 to 9 has a pattern of 4 digits when raised to an exponential power.
0 -> 0,0,0,0
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
For example:
Last digit of 7^1 = 7
Last digit of 7^2 = 9
Last digit of 7^3 = 3
Last digit of 7^4 = 1 and the pattern will repeat again
Last digit of 7^5 = 7
Last digit of 7^6 = 9
So we mod the e by 4 and simply look up at the b row and e\%4 column.
Notice here 1$^{st}$ column corresponds to when e\%4 is 1, 2$^{nd}$ column corresponds to when e\%4 is 2, 3$^{rd}$ when e\%4 is 3 and 4$^{th}$ when e\%4 is 0.
AUTHOR’S SOLUTIONS:
Author’s solution can be found here.