cppAcademy
FROM LEARNING TO COMPETING

Intermediate.
Put your skills to the test.

Bulgarian Informatics Group D · 2007–2026

270 independently explained problems: 54 Municipal, 54 Regional, 105 National Olympiad and 57 Autumn Tournament tasks. Start with the easier tasks and work upwards. Difficulty labels are learning estimates, not official ratings; Group D also includes challenging national-level problems. The six 2017 National tasks shared by Groups C and D use their existing permanent URLs. Years follow Arena’s competition-season labels. Source clarifications and special grader requirements are noted on affected tasks.
GROUP D2019 · EasyBig integers

Largest Remainder

Autumn Tournament (2019)

Submission name: max.cpp

Solve in Editor →

Problem summary

Given N positive integers with at least two distinct values, find the largest possible remainder ai mod aj over all choices of i and j. Values can have up to 50 decimal digits.

Input

N, followed by the N positive decimal integers.

Output

The maximum remainder.

Constraints

1 < N < 500,000; 0 < ai < 10^50; at least two distinct values occur. For at least 65% of tests, ai < 10^17.

Worked example

Official statement sample.

Input

5
3 12 5 8 5

Output

8

Solution analysis

  1. Let M be the largest distinct value and S the second-largest distinct value. Choosing dividend S and divisor M yields remainder S, because S < M. This already gives an achievable candidate.
  2. No remainder can exceed S. If its divisor is at most S, the remainder is smaller than that divisor. If its divisor is M, every smaller dividend is at most S and M itself gives zero. Therefore the answer is exactly S; no big-integer division is needed.
  3. Maintain the two greatest distinct values while reading the input. Compare positive decimal strings by length first and lexicographically second. Ignore another occurrence of the current maximum. Normalizing leading zeroes makes this comparison robust.
  4. In 3, 12, 5, 8, 5, the maximum is 12 and the next distinct value is 8. The choice 8 mod 12 = 8 attains the answer, while every other remainder is at most 8.

Why it works

S mod M = S proves attainability. For any pair, a divisor below M is at most S and its remainder is strictly smaller than it. A divisor equal to M gives either zero or a dividend no larger than S. These cases cover every pair and prove optimality. The streaming update preserves the two greatest distinct values after each input.

Complexity: O(NL) time and O(L) extra space, where L ≤ 50 is the maximum digit count. Only the current value and two best values are stored; each comparison inspects at most L digits.

Watch out. The answer is the second-largest distinct value, not the second array element after sorting with duplicates. ai may exceed 64-bit integers. This shortcut relies on positive values and on allowing a smaller dividend than the divisor.

Commented C++17 solution

An independently written complete program with standard headers.

#include<iostream>
#include<string>
using namespace std;
bool larger(const string&first,const string&second){
    if(first.size()!=second.size()){
        return first.size()>second.size();
    }
    return first>second;
}
int main(){
    int n;
    cin>>n;
    string maximum,second;
    for(int i=0;i<n;i++){
        string value;
        cin>>value;
        size_t firstNonzero=value.find_first_not_of('0');
        value=firstNonzero==string::npos?"0":value.substr(firstNonzero);
        if(value==maximum){
            continue;
        }
        if(maximum.empty()||larger(value,maximum)){
            // The old maximum becomes the second-largest distinct value.
            second=maximum;
            maximum=value;
        }
        else if(second.empty()||larger(value,second)){
            second=value;
        }
    }
    cout<<second<<'\n';
}

Source: Arena Olimpiici ↗