PROBLEM LINK:
Author: Ankush Khanna
DIFFICULTY:
Easy-Medium
PREREQUISITES:
AM-GM Inequality, Modular Arithmetic, Modular Inverse, Fast Exponentiation, Fermat’s Little Theorem, Mathematics
PROBLEM:
Given the size N of a sequence of numbers, and the sum S of that sequence, find the maximum product of this sequence, and print it modulo (10^9 + 7).
QUICK EXPLANATION:
Key to AC: The answer to this problem is ((\frac {S} {N})^N \bmod (10^9 + 7)) \space, using AM-GM Inequality. Here, using modular arithmetic, we can find the modular inverse of N^N \bmod (10^9 + 7) \space, using techniques like Fermat’s Little Theorem and then do modular multiplication with S^N \bmod (10^9 + 7). Everything is explained in detail in the explanation part.
EXPLANATION:
Let’s first see what all Mathematics we need to know in order to solve this problem. Let’s, for the sake of comfort, name the sequence as A. First of all, let me state the problem mathematically,
You are given with $S = (\sum_{i = 1}^{N} A_i)$, and it is also mentioned that $N$ and $S$ are positive $integers$ and that $N \leq S$. Also, $A_i \gt 0$, for each valid $i$ and $A_i$ is a $number$. Now, you need to maximize a $number \space P$, such that $P = (\prod_{i = 1}^{N} A_i)$.Now, first understand what AM-GM inequality is, and why is it important here. It is stated mathematically as:
$\frac {\sum_{i = 1}^{N} A_i} {N} \geq (\prod_{i = 1}^{N} A_i)^{(\frac {1} {N})}$ $\implies \frac {S} {N} \geq \sqrt[N]{P}$ $\therefore (\frac {S} {N})^N \geq P$ $i.e.$, Arithmetic Mean (AM) $\geq$ Geometric Mean (GM), and both of them are equal if and only if for each valid pair $(i, j), \space A_i = A_j, \space where \space i \neq j$ (which is the condition for GM to be maximum possible) $\therefore \space$ to keep the product maximum, we will keep all the elements of $A$ equal. $\therefore \space P = (\frac {S} {N})^N$ (maximum possible value of $P$) $\implies \space A_i = \frac {S} {N}$ (which is the Arithmetic Mean), for each valid $i$Also, one needs to understand that integers are different from numbers. Numbers can be anything. They can be integer, fraction, irrational, real, complex, etc.
But, here, it can be proved that P is always a rational number and can be expressed in the form of \frac {X} {Y}, \space Y \neq 0 and both X and Y are positive integers. It is very clear here, we don’t even need to explicitly prove it, it can be seen easily in our derived expression for P. [Integers and Numbers]
Now, it is mentioned that we need to print the answer modulo 10^9 + 7 (smallest 10 digit prime number). Therefore, we need to do something like:
$(S^N \bmod (10^9 + 7) \times modularInverse(N^N) \bmod (10^9 + 7)) \bmod (10^9 + 7)$A basic understanding of modular arithmetic is a must for this problem. One must be clear about the rules of modular arithmetic, before attempting this problem.
We can easily do modular exponentiation in O(\log_2 N) time complexity. We can easily find the Modular Inverse of N^N using Fermat’s Little Theorem in O(\log_2 M) time, where M is a prime and M = 10^9 + 7. And, it can also be proved that, gcd(N^N, \space M) = 1, as N \lt M, and M is a prime, \therefore \space N^N can never have any common divisor with M, which is a mandatory condition for modular multiplicative inverse to exist and be unique.
Sub-Task 1
It is given than S = \alpha \times N, where \alpha is a positive integer.
\implies \space We don’t need to find the modular inverse, \because \space \alpha = \frac {S} {N}, so just printing (\alpha^N \bmod (10^9 + 7)) \space will get you 10 points. Time taken per test case would be O(\log_2 N) with O(1) auxiliary space.
Sub-Task 2
Can be solved as mentioned above in the explanation part.
Final Result = (S^N \bmod M) \times ((N^N \bmod M)^{(M - 2)}) \bmod M, where M = (10^9 + 7)
${$According to Fermat’s Little Theorem, modularInverse(X) \mod Y = X^{(Y - 2)} \bmod Y\}
COMPLEXITY:
O(\log_2 N + \log_2 M) time per test case, where M = 10^9 + 7, with O(1) auxiliary space used.
\therefore total time for each test file would be O(T \times (\log_2 N + \log_2 M)) \space, which would suffice our time constraint.
SOLUTION:
Setter’s Solution [Plain Text]
Feel free to share your approach. If you have any queries, they are always welcome.