DEV Community

loading...

Daily Challenge #250 - Last Digit of a Large Number

thepracticaldev profile image dev.to staff ・1 min read

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!

Discussion (16)

pic
Editor guide
Collapse
vidit1999 profile image
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
}
Collapse
quoll profile image
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. 👍

Collapse
qm3ster profile image
Mihail Malo

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

Collapse
vidit1999 profile image
Vidit Sarkar

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

Collapse
savagepixie profile image
SavagePixie

JavaScript

const lastDigit = (a, b) => +Math.pow(a, b).toString().slice(-1)
Collapse
qm3ster profile image
Mihail Malo

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

Collapse
quoll profile image
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?

Collapse
andreasjakof profile image
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;
}
Collapse
daviducolo profile image
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 
Collapse
citizen428 profile image
Michael Kohl

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)
Collapse
daviducolo profile image
Davide Santangelo

no digits in ruby

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

so digits.first is correct

Thread Thread
citizen428 profile image
Michael Kohl

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
Collapse
wrightdotclick profile image
Thomas 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...

Collapse
pagefile profile image
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.

Collapse
peter279k profile image
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]
Collapse
suhaskaranth profile image
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).

Solution + Pattern