TTD - Editorial

editorial
, ,
1

PROBLEM LINK:

Contest

Author: Rahul Sharma
Tester: Naman Mittal
Editorialist: Arihant Jain

DIFFICULTY:

EASY

PREREQUISITES:

Math, Observation, Array

PROBLEM:

Alice gives Bob two integers A and N. Alice defines a series as follows

Starting with A, next term in series is square of previous term i.e.

T[N] = (T[N−1])^2

T[1]=A

Since Nth term could be very large therefore she asks Bob to tell the unit digit of Nth term. Bob is currently busy with his homework can you solve this for him ?

QUICK EXPLANATION:

Observe the pattern which is being formed by the last digits of some of the initial terms of the sequence.

EXPLANATION:

  1. As we are only concerned with the last digit, the optimal approach would be to take the last digit of the testcase.

  2. Find some initial terms of the sequence being formed for all the numbers from 0 to 9.

  3. Observe the pattern being formed.

  4. Hence, different arrays can be formed based on values of N. The resulting arrays would be as follows

    N = 1
    unitDigi t= (0,1,2,3,4,5,6,7,8,9)

    N = 2.
    unitDigit = (0, 1, 4, 9, 6, 5, 6, 9, 4, 1)

    N > 2
    unitDigit = (0, 1, 6, 1, 6, 5, 6, 1, 6, 1)

  5. Now for given A, lastDigit = A \mod 10.

    Depending upon the N, ans is simply unitDigit[lastDigit].

SOLUTIONS:

Solution 
#include<bits/stdc++.h>
using namespace std;

int main()
{
int term2[10] = {0, 1, 4, 9, 6, 5, 6, 9, 4, 1};
int termN[10] = {0, 1, 6, 1, 6, 5, 6, 1, 6, 1};

long long int t, a, n, ans;
cin >> t;
while(t--)
{
	cin >> a >> n;

	int lastDigit = a % 10;

	if (n == 1)
		ans = lastDigit;

	else if (n == 2)
		ans = term2[lastDigit];

	else
		ans = termN[lastDigit];

	cout << ans << endl;
    }

    return 0;
}