# Daily Challenge #250 - Last Digit of a Large Number

Define a function that takes in two non-negative integers `a` and `b` and returns the last decimal digit of `a^b`. Note that a and b may be very large!

For example, the last decimal digit of 9^7 is 9, since 9^7 = 4782969. The last decimal digit of (2^200)^(2^300), which has over 10^92 decimal digits, is 6. Also, please take 0^0 to be 1.

You may assume that the input will always be valid.

#### Examples

lastDigit 4 1 `shouldBe` 4
lastDigit 4 2 `shouldBe` 6
lastDigit 9 7 `shouldBe` 9

#### Tests

lastDigit 10 (10^10)

lastDigit (2^200) (2^300)

This challenge comes from dburgoyne on CodeWars. Thank you to CodeWars, who has licensed redistribution of this challenge under the 2-Clause BSD License!

Want to propose a challenge idea for a future post? Email yo+challenge@dev.to with your suggestions! Vidit Sarkar

Here is a C++ solution,

``````#include <bits/stdc++.h>
using namespace std;

unordered_map<int, vector<int>> lastDigitCycle = {
{0, {0}},
{1, {1}},
{2, {6, 2, 4, 8}},
{3, {1, 3, 9, 7}},
{4, {6, 4}},
{5, {5}},
{6, {6}},
{7, {1, 7, 9, 3}},
{8, {6, 8, 4, 2}},
{9, {1, 9}}
};

int lastDigit(long a, long b){
if((a == 0 && b == 0) || b == 0)
return 1;

int lastDigitOfA = a%10;
int len = lastDigitCycle[lastDigitOfA].size();
int reqIndex = b%len;
return lastDigitCycle[lastDigitOfA][reqIndex];
}

int main(){
cout << lastDigit(4, 1) << "\n"; // output -> 4
cout << lastDigit(4, 2) << "\n"; // output -> 6
cout << lastDigit(9, 7) << "\n"; // output -> 9
cout << lastDigit(1, 0) << "\n"; // output -> 1
cout << lastDigit(2, 0) << "\n"; // output -> 1
cout << lastDigit(0, 0) << "\n"; // output -> 1
cout << lastDigit(0, 7) << "\n"; // output -> 0
cout << lastDigit(29, 157) << "\n"; // output -> 9
}
`````` Paula Gearon

This was exactly the approach I was going to take, but then thought, "What if I write down a wrong digit in my map? This is the only reason I wrote a generator. I like the idea of a map better though. 👍 Vidit Sarkar

`vector<vector<int>>` can also be used. But I think it is a bit easier to understand the mapping this way Paula Gearon

Silly, illegible Clojure code. But it works.

``````(defn s [x] (cons x (take-while #(not= x %) (rest (iterate #(mod (* x %) 10) x)))))
(defn last-digit [a b] (let [cycle (s (mod a 10))] (nth cycle (mod (dec b) (count cycle)))))
``````

The trick is how to get the input parameters. If they're strings, then that's easy:

• Take the final character of the first string, and convert to a number.
• Take the final 2 characters of the second string, and convert to a number. These numbers can be supplied instead of the original arguments.

But if the input is supposed to look like: `(2^200)` `(2^300)` then that turns into a parsing problem! We already know how to figure out the final digit for `(2^300)` (it's 6) and `(2^200)` (also 6), but how do we manage testing this? Andreas Jakof • Edited

Maybe there is some faster mathematical way. But this should do it.

``````public static int LastDigitOfAPowerB(int a, int b)
{
if (b == 0) return 1;
long res = a % 10;
for(int i =1; i<b;++i)
{
res = (res * a) % 10;
}
return (int)res;
}
`````` Alex • Edited

Spitballing something that should with integers, but it won't take arbitrarily large numbers. Also kinda untested...

``````void unsigned int LastDigitPower(unsigned long long int a, unsigned long long int b)
{
unsigned int last = static_cast<unsigned long long int>(0xf) & pow(a, b);
if(last >= 8)
{
last &= 0x9;
}
return last;
}
``````

Maybe there's a way to eliminate the if, but right now I'm not really sure ¯\_(ツ)_/¯

Technically doesn't pass I suppose but I wanted to do something that works with numbers first. peter279k

Here is the solution with Python:

``````def last_digit(n1, n2):

if n2 == 0:
return 1

last_digits = []

step = 1
while True:
number = pow(n1, step)
step += 1
last_digit = int(str(number)[-1])

if last_digit in last_digits:
break

last_digits.append(last_digit)

print(last_digits)
last_digit_index = n2 % len(last_digits) - 1

return last_digits[last_digit_index]
`````` Davide Santangelo • Edited

ruby

``````def last_digit(a, b)
(a**b).digits.first
end
``````

or

``````def last_digit(a, b)
(a**b).to_s[-1].to_i
end
`````` TJ Wright

I think this Ruby solution underestimates the complexity required with huge numbers, although the `.digits.first` is clever! Using a mod 10 solution, like some of the solutions above, would greatly reduce the time/space complexity. brilliant.org/wiki/finding-the-las... Davide Santangelo

no digits in ruby

``````12345.digits #=> [5, 4, 3, 2, 1]
``````

so digits.first is correct suhas karanth

I saw a pattern with the last digit of the results when the numbers are raised to power incrementally.
Using that, I programmed the below solution in Java. However, it needs to be improved for larger numbers (may be using BigInteger in Java). 