Given positive integers k, a and b we need to print last k digits of a^b ie.. pow(a, b).
Input Constraint: k <= 9, a <= 10^6, b<= 10^6
Examples:
Input : a = 11, b = 3, k = 2 Output : 31 Explanation : a^b = 11^3 = 1331, hence last two digits are 31 Input : a = 10, b = 10000, k = 5 Output : 00000 Explanation : a^b = 1000..........0 (total zeros = 10000), hence last 5 digits are 00000
Naive Solution
First Calculate a^b, then take last k digits by taking modulo with 10^k. Above solution fails when a^b is too large, as we can hold at most 2^64 -1 in C/C++.
Efficient Solution
The efficient way is to keep only k digits after every multiplication. This idea is very similar to discussed in Modular Exponentiation where we discussed a general way to find (a^b)%c, here in this case c is 10^k.
Here is the implementation.
C++
// C++ code to find last k digits of a^b#include <iostream>using namespace std;/* Iterative Function to calculate (x^y)%p in O(log y) */int power(long long int x, long long int y, long long int p){ long long int res = 1; // Initialize result x = x % p; // Update x if it is more than or // equal to p while (y > 0) { // If y is odd, multiply x with result if (y & 1) res = (res * x) % p; // y must be even now y = y >> 1; // y = y/2 x = (x * x) % p; } return res;}// C++ function to calculate// number of digits in xint numberOfDigits(int x){ int i = 0; while (x) { x /= 10; i++; } return i;}// C++ function to print last k digits of a^bvoid printLastKDigits(int a, int b, int k){ cout << "Last " << k; cout << " digits of " << a; cout << "^" << b << " = "; // Generating 10^k int temp = 1; for (int i = 1; i <= k; i++) temp *= 10; // Calling modular exponentiation temp = power(a, b, temp); // Printing leftmost zeros. Since (a^b)%k // can have digits less than k. In that // case we need to print zeros for (int i = 0; i < k - numberOfDigits(temp); i++) cout << 0; // If temp is not zero then print temp // If temp is zero then already printed if (temp) cout << temp;}// Driver program to test above functionsint main(){ int a = 11; int b = 3; int k = 2; printLastKDigits(a, b, k); return 0;} |
Java
// Java code to find last k digits of a^bpublic class GFG { /* Iterative Function to calculate (x^y)%p in O(log y) */ static int power(long x, long y, long p) { long res = 1; // Initialize result x = x % p; // Update x if it is more than or // equal to p while (y > 0) { // If y is odd, multiply x with result if ((y & 1) != 0) res = (res * x) % p; // y must be even now y = y >> 1; // y = y/2 x = (x * x) % p; } return (int) res; } // Method to print last k digits of a^b static void printLastKDigits(int a, int b, int k) { System.out.print("Last " + k + " digits of " + a + "^" + b + " = "); // Generating 10^k int temp = 1; for (int i = 1; i <= k; i++) temp *= 10; // Calling modular exponentiation temp = power(a, b, temp); // Printing leftmost zeros. Since (a^b)%k // can have digits less than k. In that // case we need to print zeros for (int i = 0; i < k - Integer.toString(temp).length() ; i++) System.out.print(0); // If temp is not zero then print temp // If temp is zero then already printed if (temp != 0) System.out.print(temp); } // Driver Method public static void main(String[] args) { int a = 11; int b = 3; int k = 2; printLastKDigits(a, b, k); }} |
Python3
# Python 3 code to find last # k digits of a^b# Iterative Function to calculate # (x^y)%p in O(log y) def power(x, y, p): res = 1 # Initialize result x = x % p # Update x if it is more # than or equal to p while (y > 0) : # If y is odd, multiply # x with result if (y & 1): res = (res * x) % p # y must be even now y = y >> 1 # y = y/2 x = (x * x) % p return res# function to calculate# number of digits in xdef numberOfDigits(x): i = 0 while (x) : x //= 10 i += 1 return i# function to print last k digits of a^bdef printLastKDigits( a, b, k): print("Last " + str( k)+" digits of " + str(a) + "^" + str(b), end = " = ") # Generating 10^k temp = 1 for i in range(1, k + 1): temp *= 10 # Calling modular exponentiation temp = power(a, b, temp) # Printing leftmost zeros. Since (a^b)%k # can have digits less than k. In that # case we need to print zeros for i in range( k - numberOfDigits(temp)): print("0") # If temp is not zero then print temp # If temp is zero then already printed if (temp): print(temp)# Driver Codeif __name__ == "__main__": a = 11 b = 3 k = 2 printLastKDigits(a, b, k)# This code is contributed # by ChitraNayal |
C#
// C# code to find last k digits of a^busing System;class GFG {// Iterative Function to calculate // (x^y)%p in O(log y) static int power(long x, long y, long p){ long res = 1; // Initialize result x = x % p; // Update x if it is more // than or equal to p while (y > 0) { // If y is odd, multiply x with result if ((y & 1) != 0) res = (res * x) % p; // y must be even now y = y >> 1; // y = y/2 x = (x * x) % p; } return (int) res;}// Method to print last k digits of a^bstatic void printLastKDigits(int a, int b, int k){ Console.Write("Last " + k + " digits of " + a + "^" + b + " = "); // Generating 10^k int temp = 1; for (int i = 1; i <= k; i++) temp *= 10; // Calling modular exponentiation temp = power(a, b, temp); // Printing leftmost zeros. Since (a^b)%k // can have digits less than k. In that // case we need to print zeros for (int i = 0; i < k - temp.ToString().Length; i++) Console.WriteLine(0); // If temp is not zero then print temp // If temp is zero then already printed if (temp != 0) Console.Write(temp);}// Driver Codepublic static void Main(){ int a = 11; int b = 3; int k = 2; printLastKDigits(a, b, k);}}// This code is contributed// by 29AjayKumar |
PHP
<?php// PHP code to find last k digits of a^b /* Iterative Function to calculate (x^y)%p in O(log y) */function power($x, $y, $p) { $res = 1; // Initialize result $x = $x % $p; // Update x if it is more // than or equal to p while ($y > 0) { // If y is odd, multiply x // with result if ($y & 1) $res = ($res * $x) % $p; // y must be even now $y = $y >> 1; // y = y/2 $x = ($x * $x) % $p; } return $res; } // function to calculate // number of digits in x function numberOfDigits($x) { $i = 0; while ($x) { $x = (int)$x / 10; $i++; } return $i; } // function to print last k digits of a^b function printLastKDigits( $a, $b, $k) { echo "Last ",$k; echo " digits of " ,$a; echo "^" , $b , " = "; // Generating 10^k $temp = 1; for ($i = 1; $i <= $k; $i++) $temp *= 10; // Calling modular exponentiation $temp = power($a, $b, $temp); // Printing leftmost zeros. Since // (a^b)%k can have digits less // then k. In that case we need // to print zeros for ($i = 0; $i < $k - numberOfDigits($temp); $i++) echo 0; // If temp is not zero then print temp // If temp is zero then already printed if ($temp) echo $temp; } // Driver Code$a = 11; $b = 3; $k = 2; printLastKDigits($a, $b, $k); // This code is contributed by ajit?> |
Javascript
<script>// javascript code to find last k digits of a^b /* Iterative Function to calculate (x^y)%p in O(log y) */ function power(x , y , p) { var res = 1; // Initialize result x = x % p; // Update x if it is more than or // equal to p while (y > 0) { // If y is odd, multiply x with result if ((y & 1) != 0) res = (res * x) % p; // y must be even now y = y >> 1; // y = y/2 x = (x * x) % p; } return parseInt( res); } // Method to print last k digits of a^b function printLastKDigits(a , b , k) { document.write("Last " + k + " digits of " + a + "^" + b + " = "); // Generating 10^k var temp = 1; for (i = 1; i <= k; i++) temp *= 10; // Calling modular exponentiation temp = power(a, b, temp); // Printing leftmost zeros. Since (a^b)%k // can have digits less than k. In that // case we need to print zeros for (i = 0; i < k - temp.toString().length; i++) document.write(0); // If temp is not zero then print temp // If temp is zero then already printed if (temp != 0) document.write(temp); } // Driver Method var a = 11; var b = 3; var k = 2; printLastKDigits(a, b, k);// This code contributed by gauravrajput1</script> |
Output:
Last 2 digits of 11^3 = 31
Time Complexity : O(log b)
Space Complexity : O(1)
This article is contributed by Pratik Chhajer. If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
