Given three numbers x, y and p, compute (xy) % p.
Examples :
Input: x = 2, y = 3, p = 5 Output: 3 Explanation: 2^3 % 5 = 8 % 5 = 3. Input: x = 2, y = 5, p = 13 Output: 6 Explanation: 2^5 % 13 = 32 % 13 = 6.
We have discussed recursive and iterative solutions for power.
Below is discussed iterative solution.
C++14
/* Iterative Function to calculate (x^y)%p in O(log y) */#include <iostream>using namespace std;int power(int x, int y, int p){ // Initialize answer int res = 1; // Check till the number becomes zero while (y > 0) { // If y is odd, multiply x with result if (y % 2 == 1) res = (res * x); // y = y/2 y = y >> 1; // Change x to x^2 x = (x * x); } return res % p;}int main(){ int x = 2; int y = 5; int p = 13; cout << "Power is " << power(x, y, p); return 0;}// This code is contributed by yaswanth0412 |
Java
/* Iterative Function to calculate (x^y)%p in O(log y) */class GFG { static int power(int x, int y, int p) { int res = 1; // Initialize result while (y > 0) { // If y is odd, multiply x with result if ((y & 1) != 0) res = res * x; // y must be even now y = y >> 1; // y = y/2 x = x * x; // Change x to x^2 } return res % p; } public static void main(String[] args) { int x = 2; int y = 5; int p = 13; int mod = power(x, y, p); System.out.print("Power is " + mod); }}// This code is contributed by Dharanendra L V. |
Python3
# Iterative Function to calculate (x^y)%p in O(log y)def power(x, y, p): # Initialize result res = 1 while (y > 0): # If y is odd, multiply x with result if ((y & 1) != 0): res = res * x # y must be even now y = y >> 1 # y = y/2 x = x * x # Change x to x^2 return res % p # Driver Codex = 2y = 5p = 13print("Power is ", power(x, y, p))# This code is contributed by Khushboogoyal499 |
Javascript
<script>/* Iterative Function to calculate (x^y) % p in O(log y) */function power(x, y, p){ let res = 1; // Initialize result while (y > 0) { // If y is odd, multiply x with result if (y & 1) res = res*x; // y must be even now y = y>>1; // y = y/2 x = x*x; // Change x to x^2 } return res % p;}// Driver Codelet x = 2;let y = 5;let p = 13;document.write("Power is " + power(x, y, p));// This code is contributed by _saurabh_jaiswal</script> |
C#
/* Iterative Function to calculate (x^y)%p in O(log y) */using System;class GFG { static int power(int x, int y, int p) { int res = 1; // Initialize result while (y > 0) { // If y is odd, multiply x with result if ((y & 1) != 0) res = res * x; // y must be even now y = y >> 1; // y = y/2 x = x * x; // Change x to x^2 } return res % p; } // Driver Code static public void Main() { int x = 2; int y = 5; int p = 13; Console.Write("Power is " + power(x, y, p)); }}// This code is contributed by Dharanendra L V. |
Output
Power is 6
Time Complexity: O(log2y), where y represents the value of the given input.
Auxiliary Space: O(1), no extra space is required, so it is a constant.
Efficient Approach:
The problem with the above solutions is, overflow may occur for large values of n or x. Therefore, power is generally evaluated under the modulo of a large number.
Below is the fundamental modular property that is used for efficiently computing power under modular arithmetic.
(ab) mod p = ( (a mod p) (b mod p) ) mod p For example a = 50, b = 100, p = 13 50 mod 13 = 11 100 mod 13 = 9 (50 * 100) mod 13 = ( (50 mod 13) * (100 mod 13) ) mod 13 or (5000) mod 13 = ( 11 * 9 ) mod 13 or 8 = 8
Below is the implementation based on the above property.
C++14
// Iterative C++ program to compute modular power #include <iostream>using namespace std;/* Iterative Function to calculate (x^y)%p in O(log y) */int power(long long x, unsigned int y, int p) { int res = 1; // Initialize result x = x % p; // Update x if it is more than or // equal to p if (x == 0) return 0; // In case x is divisible by 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; } // Driver code int main() { int x = 2; int y = 5; int p = 13; cout << "Power is " << power(x, y, p); return 0; } // This code is contributed by shubhamsingh10 |
Java
// Iterative Java program to compute modular power import java.io.*;class GFG { /* Iterative Function to calculate (x^y) in O(log y) */ static int power(int x, int y, int p) { int res = 1; // Initialize result x = x % p; // Update x if it is more than or // equal to p if (x == 0) return 0; // In case x is divisible by 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 res; } // Driver Code public static void main(String[] args) { int x = 2; int y = 5; int p = 13; System.out.print("Power is " + power(x, y, p)); }}// This code is contributed by Dharanendra L V. |
Python3
# Iterative Python3 program# to compute modular power# Iterative Function to calculate# (x^y)%p in O(log y) def power(x, y, p) : res = 1 # Initialize result # Update x if it is more # than or equal to p x = x % p if (x == 0) : return 0 while (y > 0) : # If y is odd, multiply # x with result if ((y & 1) == 1) : res = (res * x) % p # y must be even now y = y >> 1 # y = y/2 x = (x * x) % p return res # Driver Codex = 2; y = 5; p = 13print("Power is ", power(x, y, p))# This code is contributed by Nikita Tiwari. |
C#
using System;public class GFG{ /* Iterative Function to calculate (x^y) in O(log y) */ static int power(int x, int y, int p) { int res = 1; // Initialize result x = x % p; // Update x if it is more than or // equal to p if (x == 0) return 0; // In case x is divisible by 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 res; } // Driver Code static public void Main () { int x = 2; int y = 5; int p = 13; Console.Write("Power is " + power(x, y, p)); }}// This code is contributed by Dharanendra L V. |
PHP
<?php// Iterative PHP program to // compute modular power// Iterative Function to // calculate (x^y)%p in O(log y) function power($x, $y, $p){ // Initialize result $res = 1; // Update x if it is more // than or equal to p $x = $x % $p; if ($x == 0) return 0; 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/2 $y = $y >> 1; $x = ($x * $x) % $p; } return $res;}// Driver Code$x = 2;$y = 5;$p = 13;echo "Power is ", power($x, $y, $p);// This code is contributed by aj_36?> |
Javascript
// Iterative Javascript program to // compute modular power// Iterative Function to // calculate (x^y)%p in O(log y) function power(x, y, p){ // Initialize result let res = 1; // Update x if it is more // than or equal to p x = x % p; if (x == 0) return 0; 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/2 y = y >> 1; x = (x * x) % p; } return res;}// Driver Codelet x = 2;let y = 5;let p = 13;document.write("Power is " + power(x, y, p));// This code is contributed by _saurabh_jaiswal |
Output
Power is 6
Time Complexity: O(Log y), where y represents the value of the given input.
Auxiliary Space: O(1), as we are not using any extra space.
Modular exponentiation (Recursive)
This article is contributed by Shivam Agrawal. Please write comments if you find anything incorrect, or if 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!
