Editorial for EXUNA (Weird Modulo Problem)

PROBLEM LINK:

Practice
Contest

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)

SOLUTIONS

Setter’s Solution
Tester’s Solution

2 Likes

can you provide code in different languages