1.
Introduction
2.
Brute Force Approach
2.1.
PseudoCode
2.2.
Implementation in C++
2.2.1.
Complexity Analysis
3.
Optimised Approach
3.1.
PseudoCode
3.2.
Implementation in C++
3.2.1.
Complexity Analysis
4.
FAQs
5.
Key Takeaways
Last Updated: Mar 27, 2024

# Find the remainder when a number A raised to N factorial is divided by P

Urwashi Priya
0 upvote

## Introduction

In this blog, we will discuss a number theory problem asked frequently in Interviews.

The problem is to find the remainder when a number A raised to N factorial is divided by P.

We are asked to find: (AN!)%P.

Say, For example,

``````A=3, N=3 and P=2.
N!=3!=3*2*1=6.
A^N!=3^6=729.
(A^N!)%P=729%2=1``````

## Brute Force Approach

If we followed the brute force approach, it would take N! Time. We need to first write the function for the factorial of a number. And then perform the basic mathematical operation to calculate (A^N!)%P.

### PseudoCode

Algorithm

_________________________________________________________________

procedure factorial(int n):

__________________________________________________________________

1.  if (n == 0) return 1

2.  return n * factorial(n - 1)

end procedure

___________________________________________________________________

procedure main():

___________________________________________________________________

1.  Take input

2.  ans=pow(a,factorial(n))

3.  return ans%p

end procedure

### Implementation in C++

``````// C++ program to Find the remainder when a number A raised to N factorial is divided by P.
#include <iostream>
#include <cmath>
using namespace std;

//function to calculate factorial of a number
int factorial(int n)
{
if (n == 0)
return 1;
return n * factorial(n - 1);
}

int main()
{
int a, n, p;
cin>>a>>n>>p;
//calculating desired output
int ans=pow(a,factorial(n));
cout<<ans%p;
}``````

Output:

``````Sample Input:
2
1
2
Sample Output:
0``````

#### Complexity Analysis

Time complexity: O(N) because the factorial of a number is calculated.

Space Complexity: O(1) because no extra space is required.

Also see, Euclid GCD Algorithm

## Optimised Approach

In order to optimise our code, we will recall our concept of exponents and powers.

1. x^(a*b*c) = ((x^a)^b)^c
2. (((x^a)^b)^c)%p = (((((x^a)%p)^b)%p)^c)%p

The optimised approach to find the remainder when a number A raised to N factorial is divided by P is given below using modular exponentiation.

To calculate power, update x if x>=p by noting the remainder on dividing x by p. If x is divisible by p, return 0.

If y is odd, multiply the result with x and then note the remainder. Else right shift y by 1 bit(for division) and multiply x with x and note the remainder.

Output the result.

To calculate remainder, run a loop to calculate for powers calculated in each step.

Till now, I assume you must have got the basic idea of what has been asked in the problem statement. So, I strongly recommend you first give it a try.

try here

### PseudoCode

Algorithm

___________________________________________________________________

procedure power(long long x, long long int y, long long int p):

___________________________________________________________________

1.  res = 1

2.  x = x % p

3.  if x == 0: return 0

4. while (y > 0):

if y & 1: res = (res * x) % p

y = y >> 1

x = (x * x) % p

Return res.

end procedure

___________________________________________________________________

procedure remainder(long long int n, long long int a, long long int p):

___________________________________________________________________

1.  ans = a % p

2.  Run loop till n:

ans = power(ans, i, p)

3.  Return ans

end procedure

### Implementation in C++

``````// C++ program to find the remainder when a number A raised to N factorial is divided by P.
#include <bits/stdc++.h>
using namespace std;

long long int power(long long x, long long int y, long long int p)
{
long long int res = 1;
// Updating x
x = x % p;

// if 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
long long int remainder(long long int n, long long int a, long long int p)
{
// storing final remainder
long long int ans = a % p;

// Calculating remainder
for (long long int i = 1; i <= n; i++)
ans = power(ans, i, p);
return ans;
}

int main()
{
long long int A, N, P;
cin>>A>>N>>P;

// Function Call
cout << remainder(N, A, P) << endl;
}``````

Output:

``````Sample Input:
2
1
2
Sample Output:
0``````

#### Complexity Analysis

Time Complexity: O(N*log N).

Analysing Time Complexity:

All n elements are traversed once and then log n times because elements get right-shifted.

Space complexity: O(1).

## FAQs

1. What is modular exponentiation?
Mostly used in public-key cryptography, it is a method of exponentiation performed on modulus. Modular exponentiation is also referred to as power in modular arithmetic. It is mainly used to limit the given size of our integer coefficients in some kind of intermediate calculations and data.

2. List out the differences between modular arithmetic and ordinary arithmetic?
The result of modular arithmetic lies in the finite sets, whereas the result of ordinary arithmetic lies in infinite sets. This is because modular arithmetic involves calculating the remainders, which will be a finite integer.

3. What is the factorial of a number?
It will return the product of all numbers less than the given number inclusive of the given number.
``````For example
4!=4*3*2*1=24.``````

## Key Takeaways

This article taught us how to find the remainder when a number A raised to N factorial is divided by P by approaching the problem using the modular exponentiation concept. We discussed our problem's implementation using illustrations, pseudocode, and proper code.

We hope you could take away all critical and conceptual techniques like analysing problems by walking over the execution of the given examples and finding out the pattern followed.

Now, we recommend you practice problem sets based on number theory to master your fundamentals and enhance your learning. You can get a wide range and variety of questions similar to this on Coding Ninjas Studio

It's not the end. Must solve the problem of similar types.

Happy Coding.

Live masterclass