dev.to staff

Posted on May 28, 2020

Daily Challenge #250 - Last Digit of a Large Number

#challenge

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!

Top comments (14)

Vidit Sarkar • May 28 '20

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 • May 28 '20

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

Mihail Malo • May 29 '20

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

Vidit Sarkar • May 30 '20

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

SavagePixie • May 28 '20

JavaScript

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

Mihail Malo • May 29 '20

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

Andreas Jakof • May 28 '20 • 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;
}

Paula Gearon • May 28 '20

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?

peter279k • Jun 20 '20

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 • May 28 '20 • Edited

ruby

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

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

TJ Wright • May 29 '20

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

Alex • May 29 '20 • 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.

Davide Santangelo • May 29 '20

no digits in ruby

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

so digits.first is correct

suhas karanth • May 30 '20

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

View full discussion (14 comments)

DEV Community

Daily Challenge #250 - Last Digit of a Large Number

Examples

Tests

Top comments (14)

Read next

Advanced Networking Concepts

Enhancing Code Quality in EnglishFormatter with Static Analysis Tools

Lambda function with GraalVM Native Image - Part 4 Measuring cold and warm starts using different Lambda memory settings

GBASE数据库 | GBase 8c 500 Primary-Standby Maintenance: Common Issues and Solutions