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:
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:
#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:
#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:
#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
#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);
}
