Define a function that takes in two non-negative integers
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.
lastDigit 4 1
lastDigit 4 2
lastDigit 9 7
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 firstname.lastname@example.org with your suggestions!
Top comments (16)
Here is a C++ solution,
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_mapand not a
vector<vector<int>>can also be used. But I think it is a bit easier to understand the mapping this way
Doesn't produce correct answers for extremely high numbers due to rounding.
Silly, illegible Clojure code. But it works.
The trick is how to get the input parameters. If they're strings, then that's easy:
But if the input is supposed to look like:
(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?
Maybe there is some faster mathematical way. But this should do it.
Spitballing something that should with integers, but it won't take arbitrarily large numbers. Also kinda untested...
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.
Here is the solution with Python:
I think this Ruby solution underestimates the complexity required with huge numbers, although the
.digits.firstis 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...
no digits in ruby
so digits.first is correct
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).