CODEWITHSUNDEEP
c++algorithm
Kudayar Pirimbaev
Kudayar Pirimbaev

Reputation: 1320

C++: Last digit in an exponent - wrong answer

I'm trying to implement a simple program that takes base and exponent and output the last digit of a result of exponentiation, but online judge says that my program gives wrong answers. What could be wrong?

P.S. The constraint of a program must be 700 kb which is not a problem here (I can erase spaces and comments and use one-letter variables to avoid that problem)

#include <iostream>

using namespace std;

int main()
{
    int t; // t - number of test cases
    cin >> t;
    cin.get();
    for (int i = 0; i < t; ++i)
    {
        int base, exp; // base - base, exp - exponent
        cin >> base >> exp;
        cin.get();

        if (exp == 0)
            cout << 1 << endl;

        else if (base % 10 == 0)
            cout << 0 << endl;

        else if (base % 10 == 1)
            cout << 1 << endl;

        else if (base % 10 == 5)
            cout << 5 << endl;

        else if (base % 10 == 6)
            cout << 6 << endl;

        else if (base % 10 == 2 || base % 10 == 3 || base % 10 == 7 || base % 10 == 8)
        {
            int pattern = exp % 4; // pattern repeats every 4th exponent
            int lastDigit = base; // lastDigit - result of program

            if (pattern == 0)
                pattern = 4;

            for (int i = 1; i < pattern; ++i)
                lastDigit = (lastDigit * base) % 10;

            cout << lastDigit << endl;
        }


        else if (base % 10 == 4 || base % 10 == 9)
        {
            int pattern = exp % 2; // pattern repeats every 2nd exponent
            int lastDigit = base; // lastDigit 0 result of program

            if (pattern == 0)
                pattern = 2;

            for (int i = 1; i < pattern; ++i)
                lastDigit = (lastDigit * base) % 10;

            cout << lastDigit << endl;
        }
    }
}

Here are samples.

INPUT

3 10
6 2
7 3123123
0 1
1 0
0 0


OUTPUT

9
6
3
0
1
1

Thanks in advance.

EDIT:

Original problem: http://www.spoj.com/problems/LASTDIG/

Upvotes: 0

Views: 317

Answers (2)

interjay
interjay

Reputation: 110088

This is wrong:

int lastDigit = base; // lastDigit - result of program

You should take the modulo by 10 to get the last digit.

You do perform a modulo by 10 later, but not in all cases (not when the for loop doesn't need any iteration). So in some cases, your code will output a number that is more than one digit.

Upvotes: 6

Eric Postpischil
Eric Postpischil

Reputation: 222437

This code fails when lastDigit * base overflows.

Upvotes: 5

Related Questions