PROBLEM LINK:
Author: Shashwat Chandra
Tester: Bharat Goyal, Shashwat Chandra, Taranpreet Singh
Editorialist: Bharat Goyal
DIFFICULTY
Cakewalk
PREREQUISITES
Observations
PROBLEM
Given an array A of distinct numbers, find the maximum value of (((A_1 \bmod A_2) \bmod A_3)......) \bmod A_N over all possible orderings of (A_1, A_2, \ldots, A_N)
QUICK EXPLANATION
If the minimum element, say X, isn’t the first element of the sequence, then the value is guaranteed to be less than X. However, if we set X as the first element and calculate the expression, it always come out to be X.
EXPLANATION
Observe that for any given order A_1...A_n, the value of the expressions is bounded by min(A_2 \ldots A_n) - 1. Consider the smallest element of the sequence, X. If it is anywhere in the 2 to n range, then the expression is guaranteed to be smaller than X. Let us place X at the first position. It can be observed that X \bmod A_i for all valid i is guaranteed to be X (it’s the smallest value). Therefore, placing X at the first position is guaranteed to give us the right answer. The order of the remaining elements is irrelevant as X stays the same under the modulo condition.
Complexity
O(N)