Print the Kth Digit

Easy
0/40
Average time to solve is 15m
23 upvotes
Asked in company
Flipkart limited

Problem statement

You are given three non-negative integers N, M, and K. Your task is to print the Kth digit from the right in ‘N’ raised to the power ‘M’ that is, in N ^ M.

Note:

1) It is guaranteed that the Kth digit from the right always exists.
2) It is also guaranteed that 'K' is always less than or equal to the number of digits in N ^ M.
3) 'N' and 'M 'can’t be a 0 simultaneously.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains an integer ‘T', which denotes the number of test cases or queries to be run. Then, the T test cases follow. 

The first line of each test case contains three non-negative integers N, M, and K, as described in the problem statement.
Output Format: 
For each test case, print in a new line, an integer denoting the Kth digit in N^M from the right.

The output for each test case will be printed in a separate line.
Note: 
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 100
0 <= N <= 15
0 <= M <= 15
1 <= K <= Digits in N ^ M

Time Limit: 1sec.
Sample Input 1:
1
2 4 1
Sample Output 1:
6
Explanation for sample input 1:
2 ^ 4 = 16, and the 1st digit in 16 from the right is 6.
Sample Input 2:
1
3 3 2
Sample Output 2:
2
Explanation for sample input 2:
3^3 = 27, and the 2nd digit in 27 from the right is 2.
Hint

Think of computing directly N ^ M and find its Kth digit from the right.

Approaches (1)
Brute-Force Approach

The idea here is to use the pow function to find N raised to the power M. After finding the power, we start removing the digits from the last until we get the kth digit.

 

  • Create a long long int variable to store the power named as temp. Note that the value of N and M can go up to 15, which means N^M may not fit in the int. So, we have created a long long int type variable.
  • Make temp = pow(N,M).
  • Create an int variable to store the current digit place from the right named as cnt. Initialize it to 0.
  • Create an int variable called ans to store the answer. Initialize it to 0.
  • Run a while loop till temp > 0, here we are planning to iterate through the digits of the temp from right to left by using %10 (temp % 10 will give the last digit of temp) :
    • Find the last digit, lastDigit = temp % 10.
    • Increment the cnt by 1.
    • If cnt == K, which implies that we are at the Kth digit so, set ans equal to lastDigit and break the while loop:
    • Otherwise, we have to remove the last digit. So, just divide temp by 10,    temp /= 10.
  • Finally, return the variable ans.
Time Complexity

O(log(N ^ M)), where ‘N’ and ‘M’ are the non-negative numbers given in the problem. 

 

In the worst case, we will be iterating through all the digits of the N ^ M. Hence, the time complexity is O(log (N ^ M)).

Space Complexity

O(1).

 

As we are using only constant space.

Code Solution
(100% EXP penalty)
Print the Kth Digit
Full screen
Console