3
\$\begingroup\$

I have to make code that calculates the last digit of \$a^b\$. Here, \$a\$ can have up to 1000 digits whereas \$b\$ can be from 0 to 915*1015. Now I calculated the last digit of a and raised that single digit number to the power b and that number's last digit will be the answer.

#include <iostream>
#include <math.h>
#include <string>
using namespace std;
unsigned long long int foo (unsigned long long int a,unsigned long long int b );
int main (void)
{
    int test;
    cin>>test;
    while ( test != 0 )
    {
        string a;
        cin>>a;
        unsigned long long int b;
        cin>>b;
        char c;
        int e;
        string::iterator it = a.end()-1;
        c = *it;
        e = c -48;
        if ( e == 0 && b == 0 )
            cout<<"0"<<"\n";
        else
        {
            unsigned long long modu  = foo(e,b);
            cout<<modu<<"\n";
            test--;
        }
    }
    return 0;
}



unsigned long long int foo (unsigned long long int a,unsigned long long int b )
{
    unsigned long long int ret;
    if ( b == 0 )
        return 1;
    if ( b % 2 == 0 )
    {
        ret = foo(a,b/2);
        ret = ret*ret;
    }
    else if ( b % 2 != 0 )
    {
        ret = foo(a,b/2);
        ret = ret*ret;
        ret = ret*a;
    }
    return ret%10;
}

However, I don't know why this shows WA on submitting it? Any corner cases that I might be missing?

\$\endgroup\$
5
\$\begingroup\$

Wrong answer

$$ everything^0 = 1 => 0^0 = 1$$

    if ( e == 0 && b == 0 )
        cout<<"0"<<"\n";

Solution

Last digit relay only on last digit and you can not look at digits than goes before last one. As your power is up to \$10^{18}\$ you have to use modular binary power function.

Here is my solution:

#include <iostream>
#include <string>

typedef unsigned long long int ULLI;
typedef unsigned int UI;

UI bin_pow(UI a, ULLI n) {
    UI result = 1;
    while (n) {
        if (n & 1) {
            result = (result * a) % 10;
            n -= 1;
        } else {
            a = (a * a) % 10;
            n >>= 1;
        }
    }
    return result;
}

int main(int argc, char *argv[]) {
    int n;
    std::cin >> n;
    while (n--) {
        std::string a;
        ULLI b;
        std::cin >> a >> b;
        std::cout << bin_pow(a.back() - '0', b) << std::endl;
    }
}

C++11 std::string

Since C++11 std::basic_string had method .back() that returns last char in the string.

To do this with C++98 you can use .rbegin() iterator.

Solution with complexity \$O(1)\$

Previous code can be acceptable solution, but if it will still not be enough, try to set predefined array for length of circle when

$$ a^{length} mod(10) = a | a = [0 \ldots 9]$$

I'd write some Python script, lets take a look at the results:

(2, [2, 4, 8, 6, 2, 4, 8, 6, 2, 4, 8])
(3, [3, 9, 7, 1, 3, 9, 7, 1, 3, 9, 7])
(4, [4, 6, 4, 6, 4, 6, 4, 6, 4, 6, 4])
(5, [5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5])
(6, [6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6])
(7, [7, 9, 3, 1, 7, 9, 3, 1, 7, 9, 3])
(8, [8, 4, 2, 6, 8, 4, 2, 6, 8, 4, 2])
(9, [9, 1, 9, 1, 9, 1, 9, 1, 9, 1, 9])

What does it means? First number is the digit which was processed. Array is array of lower digits from previous equation. As you can see, there are not too many circles of repetitions.

Lets take a look at digit 2:

  • with power of 1 we have \$2^1 mod(10)=2\$
  • with power of 2 we have \$2^2 mod(10)=4\$
  • with power of 3 we have \$2^3 mod(10)=8\$
  • with power of 4 we have \$2^4 mod(10)=6\$
  • with power of 5 we have \$2^5 mod(10)=2\$

that's it, we've got the circle for digit 2.

Also digits may be grouped by number of powers before lower digit will be repeated.

  • 2, 3, 7, 8 repeated after 4 power operations
  • 1, 5, 6 repeated after each power opetation
  • 4, 9 repeated each 2nd power operation
const unsigned int predefined[10][4] = {
    {0},
    {1},
    {2,4,8,6},
    {3,9,7,1},
    {4,6},
    {5},
    {6,4},
    {7,9,3,1},
    {8,4,2,6},
    {9,1}
};

unsigned int bin_pow(const unsigned int& a, unsigned long long int n) {
    if (!n) return 1;

    switch(a) {
        case 0:
        case 1:
        case 5:
            return a;
        case 2:
        case 4:
        case 7:
        case 8:
            return predefined[a][n & 3];
        default:
            return predefined[a][n & 1];
    }
}
\$\endgroup\$
  • \$\begingroup\$ Everything unless a == 0... Just nitpicking. \$\endgroup\$ – vnp Oct 2 '14 at 18:57
  • \$\begingroup\$ @outoftime, I have a doubt. What are the errors in my code apart from 0^0 = 1? I didn't quite understand the statement, Last digit relay only on last digit and you can not look at digits than goes before last one. Thanks. \$\endgroup\$ – Qirohchan Oct 2 '14 at 19:04
  • \$\begingroup\$ @Qirohchan, where are you going, look at my O(1) solution (: \$\endgroup\$ – outoftime Oct 2 '14 at 19:51
  • \$\begingroup\$ As much as I am getting it, I am still having confusion in the cases. Can you elaborate on it a little bit. Thanks! \$\endgroup\$ – Qirohchan Oct 2 '14 at 20:02
  • \$\begingroup\$ Let us continue this discussion in chat. \$\endgroup\$ – outoftime Oct 2 '14 at 20:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.