# Maths: Inverse Mod & Problems

---
## Trailing Zeros in Factorial

Given a integer N, find the count of trailing zeros in the factorial n!.

**Example**, 5! = 120 and it has 1 trailing zeros.

Input :
5

Output :
1

**For example**, 20!=2432902008176640000 and it has 4 trailing zeros.

Input :
20

Output :
4

### Idea

How many trailing zeros does N! have? In other words, how many times can we divide N! by 10 until it's no longer divisible by 10.

### Approach
One way of finding this out is by looking at the prime factorization of N!. If 10 divides N! then the prime factorization of 10 must be contained in the prime factorization of N! and since 10=2x5 then the question becomes how many pairs {2,5} are in N! prime factorization.

<img src="https://d2beiqkhq929f0.cloudfront.net/public_assets/assets/000/065/965/original/Screenshot_2024-02-22_at_4.24.12_PM.png?1708599262" width=500 />

Since 2 is a much more common factor and the pair requires both numbers to be present the answer becomes the number of times 5 appears in N! prime factorization. Given that N! is the product of all positive integers less than or equal to N we can conclude that the answer is the number of times 5 comes up in the prime factorization of all integers belonging to the interval [1, N].

### Example
Let's calculate the number of trailing zeros in 10! (10 factorial), which is the product of all positive integers from 1 to 10:

10! = 10 × 9 × 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1

First, factor these numbers into their prime factors:

10 = 2 × 5
9 = 3²
8 = 2³
7 = 7
6 = 2 × 3
5 = 5
4 = 2²
3 = 3
2 = 2
1 = 1 (does not contribute to prime factors)
In this factorization, we focus on how many times the number 5 appears:

One 5 comes from the number 10.
Another 5 comes from the number 5.
So, we have two 5s.

Considering there are plenty of 2s to pair with these 5s (from 10, 8, 6, 4, and 2), we can form two pairs of 2 and 5, meaning 10! has two trailing zeros.

### Solution
To solve this problem we must take into account every multiple of every power of five less than N.

Basically,
For every 5 numbers, there's at least one that is a multiple of 5 (e.g., 5, 10, 15...), and for every 25 numbers, there's at least one number that is a multiple of 25 (which counts as two 5s, like 25 = 5 * 5), and so on. This pattern means we need to count not just the simple multiples of 5 but also the multiples of higher powers of 5 (like 25, 125, etc.) because they contribute more 5s.

<img src="https://d2beiqkhq929f0.cloudfront.net/public_assets/assets/000/065/967/original/Screenshot_2024-02-22_at_4.31.40_PM.png?1708599764" width="500" />

By following this pattern, you can calculate the number of trailing zeros for any factorial N! by sequentially dividing N by 5, then 25, then 125, and so on, adding up all these counts, until the quotient from division becomes less than 1.

### Pseudocode

int findTrailingZeros(int n) {
    int count = 0;

    // Keep dividing n by powers of 5 and update count
    for (int i = 5; n / i >= 1; i *= 5) {
        count += n / i;
    }

    return count;
}

---
### PubG - Find min health of surviving player

There are N players playing a game, each player has a health of A[i].

If the ith player attack the jth player then,
* If A[i] >= A[j] then Player j will die.
* If A[i] < A[j] then A[j] becomes A[j] - A[i]

You need to find the **minimum health** of the last standing player.

**Example 1:**

Input: [2, 4, 6]
Output: 2

**Example 2:**

Input: [10, 6]
Output: 2

### Dry Run

Lets take 2 players, and visualize how they end up the match.

the players health as [10, 6].

<img src="https://d2beiqkhq929f0.cloudfront.net/public_assets/assets/000/069/253/original/gcd.png?1711570257" width=500px>

At the end, the result may be (10, 0), (0, 6), (4, 0), (2, 0), (0, 2).

We came to know that, the possible last standing player have the health of 10, 6, 4, 2, 2.

The minimum health among the possibilities is 2.

### Observation


Here, we can observe that, the minimum health is the GCD of the Entire array.

### Pseudo Code

ans = arr[0]
for(i = 0; i < n; i++){
	ans = gcd(ans, arr[i]);
}
return ans;

### Complexity

**Time Complexity:** O(N log(max of array))
**Space Complexity:** O(1)

---
### Find nCr % P

$nCr = n! / ((n - r)! * r! )$

Can we open (a/b)%M same as how we have been doing with other arithmetic properties ? Let's try!

$(a/b) \% M = ( a\%m / b\%m ) \% M$

Say,
a = 16, b = 4, M = 5

$(16/4) \% 5 = 4$

$(16 \% 5 / 4\% 5) \% 5 = 0$

LHS is not same as RHS hence the above formula is not valid!

### Correct Formular for Mod with division

$(a / b) \% M = (a * b^{-1}) \% M = (a \% M *~ b^{-1} ~\% M) \% M$

### How do we get b^-1 % M ?

This value only exists if **gcd(b, M) = 1**

> Why?
This will not be covered since the proof is tricky & lengthy and not asked in Interviews.

Can we write `b * (1/b) = 1 ?` Yes!
Now, it can be written as: $b * b^{-1} = 1$
Taking **%M** on both sides
$(b ~\%~ M * b^{-1} ~\%~M ) \% M = 1 \% M$
$(b ~\%~ M * b^{-1} ~\%~M ) \% M = 1 ---------- (a)$

The value of $b^{-1} ~\%~M$ will lie between 0 to M - 1, but it can not be 0 as the above equation (a) will not hold true.

So, it can only lie between [1, M - 1]
One way to get $b^{-1} ~\%~M$ is to iterate over above range and check if equation (a) holds true.

**Example:**
b = 10, M = 7; $b^{-1} ~\%~M$ exists since gcd(10, 7) = 1

Let's iterate from 1 to M-1 and check.

$i = 1; (10 \% 7 * 1) \% 7 = 3 (!= 1)$

$i = 2; (10 \% 7 * 2) \% 7 = 6 (!= 1)$

$i = 3; (10 \% 7 * 3) \% 7 = 2 (!= 1)$

$i = 4; (10 \% 7 * 4) \% 7 = 5 (!= 1)$

$i = 5; (10 \% 7 * 5) \% 7 = 1 (== 1)$ [found it]

Hence, $10^{-1} \% 7 = 5$

The above approach will take O(M) time to get the answer.

---
### Fermat's Little Theorem

Fermat’s little theorem states that given b and M, $b^{-1} ~\%~M$ exists if gcd(b, M) = 1

If M is prime, $b^{M-1} ~\%~M = 1$

***Multiply $b^{-1} ~\%~M$ on both sides,***

$((b^{M-1}) \% M * b^{-1} \% M ) \% M = 1 * b^{-1} ~\%~M$

$(b^{M-1} * b^{-1}) \% M = 1 * b^{-1} ~\%~M$

$b^{M-2} ~\%~M = 1 * b^{-1} ~\%~M$

***It implies that,***
$b^{-1} ~\%~M = b^{M-2} ~\%~M$

which means we will just have to find $b^{M-2} ~\%~M$ to get $b^{-1} ~\%~M$

$b^{M-2} ~\%~M$ can be computed in **log N** time using fast power method.