|
Given three numbers a, b and k, find k-th digit in ab from right side
Examples:
Input : a = 3, b = 3, k = 1
Output : 7
Explanation: 3^3 = 27 for k = 1. First digit is 7 in 27
Input : a = 5, b = 2, k = 2
Output : 2
Explanation: 5^2 = 25 for k = 2. First digit is 2 in 25
Method
1) Compute a^b
2) Iteratively remove the last digit until k-th digit is not meet
C++
<?php
function kthdigit($a, $b, $k)
{
$p = pow($a, $b);
$count = 0;
while ($p > 0 and $count < $k)
{
$rem = $p % 10;
$count++;
if ($count == $k)
return $rem;
$p = $p / 10;
}
return 0;
}
$a = 5;
$b = 2;
$k = 1;
echo kthdigit($a, $b, $k);
?>
|
Output:
5
Time Complexity: O(log p)
Auxiliary Space: O(1)
How to avoid overflow?
We can find power under modulo 10sup>k to avoid overflow. After finding the power under modulo, we need to return first digit of the power.
|
