Given three integers A, N and P, the task is to find (A^(N!)) % P.
Examples:
Input: A = 2, N = 1, P = 2
Output: 0
Explanation: As (2^(1!)) = 2
Therefore 2 % 2 will be 0.Input: A = 3, N = 3, P = 2
Output: 1
Naive Approach: The simplest solution of this problem can be find out factorial of N say f, and now calculate A to power f say pow and find its remainder with P.
Below is the implementation of the above approach:
C++
// C++ program for above approach#include <bits/stdc++.h>using namespace std;// Function to calculate factorial of a Numberlong long int fact(long long int n){ long long int ans = 1; // Calculating factorial for (long long int i = 2; i <= n; i++) ans *= i; // Returning factorial return ans;}// Function to calculate resultant remainderlong long int remainder( long long int n, long long int a, long long int p){ // Function call to calculate // factorial of n long long int len = fact(n); long long int ans = 1; // Calculating remainder for (long long int i = 1; i <= len; i++) ans = (ans * a) % p; // Returning resultant remainder return ans;}// Driver Codeint main(){ // Given Input long long int A = 2, N = 1, P = 2; // Function Call cout << remainder(N, A, P) << endl;} |
Java
// Java program for the above approachimport java.lang.*;import java.util.*;class GFG{// Function to calculate factorialstatic int fact(int n){ int ans = 1; // Calculating factorial for (int i = 2; i <= n; i++) ans *= i; // Returning factorial return ans;}// Function to calculate resultant remainderstatic int remainder( int n, int a, int p){ // Function call to calculate // factorial of n int len = fact(n); int ans = 1; // Calculating remainder for (int i = 1; i <= len; i++) ans = (ans * a) % p; // Returning resultant remainder return ans;}// Driver Codepublic static void main(String args[]){ // Given Input int A = 2, N = 1, P = 2; // Function Call System.out.println(remainder(N, A, P));}}// This code is contributed by sanjoy_62. |
Python3
# Python 3 program for above approach# Function to calculate factorial of a Numberdef fact(n): ans = 1 # Calculating factorial for i in range(2,n+1,1): ans *= i # Returning factorial return ans# Function to calculate resultant remainderdef remainder(n, a, p): # Function call to calculate # factorial of n len1 = fact(n) ans = 1 # Calculating remainder for i in range(1,len1+1,1): ans = (ans * a) % p # Returning resultant remainder return ans# Driver Codeif __name__ == '__main__': # Given Input A = 2 N = 1 P = 2 # Function Call print(remainder(N, A, P)) # This code is contributed by SURENDRA_GANGWAR. |
C#
// C# program for the above approachusing System;public class GFG{// Function to calculate factorialstatic int fact(int n){ int ans = 1; // Calculating factorial for (int i = 2; i <= n; i++) ans *= i; // Returning factorial return ans;}// Function to calculate resultant remainderstatic int remainder( int n, int a, int p){ // Function call to calculate // factorial of n int len = fact(n); int ans = 1; // Calculating remainder for (int i = 1; i <= len; i++) ans = (ans * a) % p; // Returning resultant remainder return ans;}// Driver Codepublic static void Main(string []args){ // Given Input int A = 2, N = 1, P = 2; // Function Call Console.WriteLine(remainder(N, A, P));}}// This code is contributed by AnkThon |
Javascript
<script>// Javascript program for above approach// Function to calculate factorial of a Numberfunction fact(n) { let ans = 1; // Calculating factorial for (let i = 2; i <= n; i++) ans *= i; // Returning factorial return ans;}// Function to calculate resultant remainderfunction remainder(n, a, p) { // Function call to calculate // factorial of n let len = fact(n); let ans = 1; // Calculating remainder for (let i = 1; i <= len; i++) ans = (ans * a) % p; // Returning resultant remainder return ans;}// Driver Code// Given Inputlet A = 2, N = 1, P = 2;// Function Calldocument.write(remainder(N, A, P));// This code is contributed by _saurabh_jaiswal.</script> |
Output:
0
Time complexity: O(N!)
Auxiliary Space: O(1)
Efficient Approach: The above can be optimized using concept of modular exponentiation and some properties of modulo and powers:
- x^(a*b*c) can be written as :- (((x^a)^b)^c) …property of power.
- ((x^a)^b) % p can be written as :- ((x^a) %p)^b) % p …property of modulo.
Below is the implementation of the above approach:
C++
// C++ program for above approach#include <bits/stdc++.h>using namespace std;// Function to calculate// (A^N!)%P in O(log y)long long int power( long long x, long long int y, long long int p){ // Initialize result long long int res = 1; // Update x if it is more than or // Equal to p x = x % p; // In case x is divisible by 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 >> 1; x = (x * x) % p; } // Returning modular power return res;}// Function to calculate resultant remainderlong long int remainder( long long int n, long long int a, long long int p){ // Initializing ans //to store final remainder long long int ans = a % p; // Calculating remainder for (long long int i = 1; i <= n; i++) ans = power(ans, i, p); // Returning resultant remainder return ans;}// Driver Codeint main(){ // Given Input long long int A = 2, N = 1, P = 2; // Function Call cout << remainder(N, A, P) << endl;} |
Java
/*package whatever //do not write package name here */import java.io.*;class GFG { static long power(long x, long y, long p) { // Initialize result long res = 1; // Update x if it is more than or // Equal to p x = x % p; // In case x is divisible by 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; x = (x * x) % p; } // Returning modular power return res; } // Function to calculate resultant remainder static long remainder(long n, long a, long p) { // Initializing ans to store final remainder long ans = a % p; // Calculating remainder for (long i = 1; i <= n; i++) ans = power(ans, i, p); // Returning resultant remainder return ans; } // Driver Code public static void main(String[] args) { // Given Input long A = 2, N = 1, P = 2; // Function Call System.out.println(remainder(N, A, P)); }}// This code is contributed by maddler. |
Python3
# Python program for above approach# Function to calculate# (A^N!)%P in O(log y)def power(x, y, p): # Initialize result res = 1 # Update x if it is more than or # Equal to p x = x % p # In case x is divisible by 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 >> 1 x = (x * x) % p # Returning modular power return res# Function to calculate resultant remainderdef remainder(n, a, p): # Initializing ans #to store final remainder ans = a % p # Calculating remainder for i in range(1,n+1): ans = power(ans, i, p) # Returning resultant remainder return ans# Driver Code# Given InputA = 2N = 1P = 2# Function Callprint(remainder(N, A, P))# This code is contributed by shivanisinghss2110 |
C#
/*package whatever //do not write package name here */using System;class GFG { static long power(long x, long y, long p) { // Initialize result long res = 1; // Update x if it is more than or // Equal to p x = x % p; // In case x is divisible by 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; x = (x * x) % p; } // Returning modular power return res; } // Function to calculate resultant remainder static long remainder(long n, long a, long p) { // Initializing ans to store final remainder long ans = a % p; // Calculating remainder for (long i = 1; i <= n; i++) ans = power(ans, i, p); // Returning resultant remainder return ans; } // Driver Code public static void Main(String[] args) { // Given Input long A = 2, N = 1, P = 2; // Function Call Console.Write(remainder(N, A, P)); }}// This code is contributed by shivanisinghss2110 |
Javascript
<script> // JavaScript Program to implement // the above approach // Function to calculate // (A^N!)%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; // In case x is divisible by 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 >> 1; x = (x * x) % p; } // Returning modular power return res; } // Function to calculate resultant remainder function remainder(n, a, p) { // Initializing ans // to store final remainder let ans = a % p; // Calculating remainder for (let i = 1; i <= n; i++) ans = power(ans, i, p); // Returning resultant remainder return ans; } // Driver Code // Given Input let A = 2, N = 1, P = 2; // Function Call document.write(remainder(N, A, P) + "<br>");// This code is contributed by Potta Lokesh </script> |
Output:
0
Time complexity: O(N*logN)
Auxiliary Space: O(1)
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!
