Given two integers a and b as strings, the task is to find the last digit of a^b. The challenge is that both numbers can contain up to 1000 digits, making it impossible to convert them into standard numeric data types.
Understanding the Problem
Consider the example:
a = "3"
b = "10"
We need to find the last digit of:
3^10 = 59049
The answer is:
9
At first glance, computing a^b directly seems necessary. However, since a and b can be extremely large, this approach is not feasible.
Key Observation
To determine the last digit of a number, only the last digit of its base matters.
For example:
23^10 and 3^10
Both will have the same last digit because only the final digit 3 influences the final digit of the result.
So instead of using the entire value of a, we only need:
int lastDigit = a.charAt(a.length() - 1) - '0';
Pattern of Last Digits
Let's examine powers of 2:
2^1 = 2 -> 2
2^2 = 4 -> 4
2^3 = 8 -> 8
2^4 = 16 -> 6
2^5 = 32 -> 2
2^6 = 64 -> 4
The last digits repeat:
2, 4, 8, 6
This cycle length is 4.
Similarly:
3 -> 3, 9, 7, 1
4 -> 4, 6, 4, 6
7 -> 7, 9, 3, 1
8 -> 8, 4, 2, 6
An important mathematical fact is that the last digit pattern for any number repeats every 4 powers (or fewer).
Therefore, instead of finding b, we only need:
b % 4
Why Compute b % 4?
Suppose:
b = 10
Then:
10 % 4 = 2
For base 3:
Cycle: 3, 9, 7, 1
Index: 1, 2, 3, 4
Since remainder is 2, we take the second value:
9
which is the correct answer.
Handling Very Large b
Since b may contain up to 1000 digits, it cannot fit into an integer.
We compute b % 4 digit by digit:
int mod = 0;
for (int i = 0; i < b.length(); i++) {
mod = (mod * 10 + (b.charAt(i) - '0')) % 4;
}
This technique is commonly used when working with extremely large numbers represented as strings.
Special Case
If:
b = "0"
then:
a^0 = 1
for any non-zero value of a.
Therefore:
if (b.equals("0")) {
return 1;
}
Step-by-Step Example
Input:
a = "23"
b = "10"
Extract last digit:
3
Compute:
10 % 4 = 2
Cycle for 3:
3, 9, 7, 1
Position 2 gives:
9
Answer:
9
Java Code
class Solution {
public int getLastDigit(String a, String b) {
// Any number raised to power 0 is 1
if (b.equals("0")) {
return 1;
}
// Last digit of base
int lastDigit = a.charAt(a.length() - 1) - '0';
// Compute b % 4
int mod = 0;
for (int i = 0; i < b.length(); i++) {
mod = (mod * 10 + (b.charAt(i) - '0')) % 4;
}
// If remainder is 0, use 4th position in cycle
int exponent = (mod == 0) ? 4 : mod;
int result = 1;
for (int i = 0; i < exponent; i++) {
result = (result * lastDigit) % 10;
}
return result;
}
}
Dry Run
Input:
a = "6"
b = "2"
Last digit of base:
6
Compute:
2 % 4 = 2
Calculate:
6^2 = 36
Last digit:
6
Output:
6
Complexity Analysis
Time Complexity
O(|b|)
We traverse the string b once to compute b % 4.
Auxiliary Space
O(1)
Only a few variables are used regardless of input size.