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 [e-mail] with your suggestions!

Comments

[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]

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

[Alex]

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.

[Davide Santangelo]

no digits in ruby

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

so digits.first is correct

[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?

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

[Mihail Malo]

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

[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]

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

[SavagePixie]

JavaScript

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

[Mihail Malo]

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

[Davide Santangelo]

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

[Andreas Jakof]

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