How to Get Last Digit of a Large Number in C

The challenge

Define a function that takes in two non-negative integers aaa and bbb and returns the last decimal digit of aba^bab. Note that aaa and bbb 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 */
Code language: C++ (cpp)

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; }
Code language: C++ (cpp)

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]; }
Code language: C++ (cpp)

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; }
Code language: C++ (cpp)

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); }
Code language: C++ (cpp)
Tags:
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments