MAXREM - Editorial

cakewalk
editorial
april19

#1

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.


#2

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