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

Daily Challenge (258 Part Series)

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!

Daily Challenge (258 Part Series)

### Discussion 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
}


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. 👍

Why is the outer a unordered_map and not a vector?
It's consecutive?

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

JavaScript

const lastDigit = (a, b) => +Math.pow(a, b).toString().slice(-1)


Doesn't produce correct answers for extremely high numbers due to rounding.

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;
}


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?

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]


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.

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


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...

digits.first should probably be digits.last, right?

This won't work for big numbers btw, the last example will raise an exception:

last_digit(2**200, 2**300)
(irb):2: warning: in a**b, b may be too big
Traceback (most recent call last):
...
NoMethodError (undefined method digits' for Infinity:Float)


no digits in ruby

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


so digits.first is correct

Ah yes, somehow I was thinking this would have the same order as chars.to_a, but it doesn't, so you can easily get back the number:

[5, 4, 3, 2, 1].each.with_index.reduce(0) do |result, (n, i)|
result + n * 10 ** i
end
#=> 12345
`

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).   