The challenge

Define a function that takes in two non-negative integers aa_a_ and bb_b_ and returns the last decimal digit of aba^b_a__b_. Note that aa_a_ and bb_b_ may be very large!

For example, the last decimal digit of 979^797 is 999, since 97=47829699^7 = 478296997=4782969. The last decimal digit of (2200)2300({2^{200}})^{2^{300}}(2200)2300, which has over 109210^{92}1092 decimal digits, is 666. Also, please take 000^000 to be 111.

You may assume that the input will always be valid.

Examples:

1
2
3
4

last_digit("4", "1")            /* returns 4 */
last_digit("4", "2")            /* returns 6 */
last_digit("9", "7")            /* returns 9 */ 
last_digit("10","10000000000")  /* returns 0 */

The solution in C

Option 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

#include <math.h>
#include <string.h>

int last_digit(const char *a, const char *b)
{
    // exponent = 0
    if (*b == 48) {return 1;}
    // base = 0
    if (*a == 48) {return 0;}
    
    // take least significant digit of a
    int x = a[strlen(a)-1] - 48;
    // take two least significants digit of a
    int y = (b[strlen(b)-1] - 48);
    if (strlen(b)>1) { y += (b[strlen(b)-2] - 48) * 10;}
  
    y = y%4 + 4;  
    return (int) pow(x,y) % 10;
}

Option 2:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

#include <string.h>

int last_digit(const char *a, const char *b) {
  if(b[0] == '0') return 1;
  if(a[0] == '0') return 0;
  int la = a[strlen(a) - 1] - 48;
  if(la == 0) return 0;
  int lb = (strlen(b) == 1) ? (b[0] - 48)%4 : ((b[strlen(b)-2]-48)*10 + b[strlen(b)-1] - 48)%4;
  int table[10][4] = {{0,0,0,0}, {1,1,1,1},
                   {6,2,4,8}, {1,3,9,7},
                   {6,4,6,4}, {5,5,5,5},
                   {6,6,6,6}, {1,7,9,3},
                   {6,8,4,2}, {1,9,1,9}};
  return table[la][lb];
}

Option 3:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

#include <string.h>
#include <math.h>
int last_digit(const char *a, const char *b)
{
    int lastDigitA = a[strlen(a) - 1] - '0';
    size_t lenB = strlen(b);
  
    if(lenB == 1 && b[0] - '0' == 0) return 1;
    int mod = 0;
  
    for(int i = 0; i < lenB; i++){
      int d = b[i] - '0';
      mod = (mod * 10 + d) % 4;
    }
  
    return (int)(pow(lastDigitA, 4+mod)) % 10;
}

Test cases to validate our solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

#include <criterion/criterion.h>

extern int last_digit(const char *a, const char *b);

static void assert_data(const char *a, const char *b, int expected)
{
    int actual = last_digit(a, b);
    if (actual != expected)
        cr_assert_fail("*Actual*: %d\nExpected: %d\n  a: %s\n  b: %s", actual, expected, a, b);
    else
        cr_assert(1);
}

Test(Sample_Test, should_return_the_last_digit)
{
    assert_data("4", "1", 4);
    assert_data("4", "2", 6);
    assert_data("9", "7", 9);
    assert_data("10", "10000000000", 0);
    assert_data(
        "1606938044258990275541962092341162602522202993782792835301376",
        "2037035976334486086268445688409378161051468393665936250636140449354381299763336706183397376",
        6
    );
    assert_data(
        "3715290469715693021198967285016729344580685479654510946723",
        "68819615221552997273737174557165657483427362207517952651",
        7
    );
    assert_data("243", "0", 1);
    assert_data("0", "94907", 0);
}