Daily Challenge #94 - Last Digit

For a given list [x1, x2, x3, ..., xn] compute the last (decimal) digit of x1 ^ (x2 ^ (x3 ^ (... ^ xn))).

E. g.,
last_digit([3, 4, 2]) == 1
because 3 ^ (4 ^ 2) = 3 ^ 16 = 43046721.

Beware: Powers grow incredibly fast. For example, 9 ^ (9 ^ 9) has more than 369 million of digits. lastDigit has to deal with such numbers efficiently.

Corner cases: We assume that 0 ^ 0 = 1 and that lastDigit of an empty list equals to 1.

---

This challenge comes from Bodigrim on 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

[erezwanderman]

Javascript:

  const last_digit = ([...a]) => {
    while (a.length > 1) {
      [x, y] = a.splice(-2);
      a.push(((x % 10) ** ((y - 1) % 4 + 1)) % 10);
    }
    return a[0] || 1;
  }

[Giang Vincent]

can we have some explain please ?

[erezwanderman]

Yes.
Let's look at a spreadsheet of x^y % 10.

For x, the values repeat every 10, that is, x^y % 10 == (x+10)^y % 10.
For y, the values repeat every 4, that is, x^y % 10 == x^y+4 % 10, except for the case y=0.
Why is it so? I don't know, maybe someone else can explain/prove the math. All I know is that I can use it to make the power calculations much smaller. If I need the last digit of 345435^456, I calculate instead the last digit of (345435%10)^(456-1%4+1)=5^3=125, which is 5.

So that's what I'm doing in the function, extracting the last two numbers out of the array, calculating the right-most digit of their power and pushing it back. I also handle the case of empty list as per the requirements, not sure why they wanted it to be 1.

[Balaji K]

Javascript

const lastDigit = (digits) => {
  if(!digits.length) return '1';
  let power = digits.reduceRight((a, b) => Math.pow(b, a));

  power = (!isFinite(power) || isNaN(power)) ? '0' : String(power);

  return power.slice(power.length - 1, power.length);
}

lastDigit([9, 9]); Output: '9'
lastDigit([9, 9, 9]); Output: '0'
lastDigit([]); Output: '1'

Not sure how to get the last digit from more than 369 million of digits, so handled it with 0 and empty list as 1.