MAXREM - Editorial

PROBLEM LINK:

Practice
Contest, div. 1
Contest, div. 2

Author: Raj Shah
Tester: Zhong Ziqian
Editorialist: Oleksandr Kulkov

DIFFICULTY:
CAKEWALK
PREREQUISITES:
None
PROBLEM:
You’re given sequence A_1, \dots, A_n. Find out maximum possible A_i \bmod A_j.
QUICK EXPLANATION:
Sort in descending order, remove duplicates. Answer is A_2 \bmod A_1 now.
EXPLANATION:
If all numbers are equal, answer is 0. Otherwise let largest element in sequence be a and second largest element which is not equal to a be b. Note that b \bmod a = b, now if A_i \bmod A_j > b then A_j > b, thus A_j = a. But since all elements are at most a, largest remainder modulo a is b:

int main() {
	int n;
	cin >> n;
	int a[n];
	for(int i = 0; i < n; i++) {
		cin >> a[i];
	}
	sort(a, a + n, greater<int>());
	unique(a, a + n);
	cout << a[1] % a[0] << endl;
	return 0;
}

AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.
Editorialist’s solution can be found here.

instead of sorting and removing duplicates, we can simply find max and second max. This will have better time complexity.

7 Likes

Seems there is problem with this in python, half the test cases are accepted with AC.
Remaining test cases are giving NZEC error. I have no clue of how and why is this happening.

 n = int(input()) 
 l = list(map(int, input().split())) 
 l = list(set(l))
 l.sort()
 print(l[-2] % l[-1])

Please check this with Python 3.6.
https://www.codechef.com/viewsolution/24459926)