Maximum Value (Codeforces 484B)
Tags: Math, two pointers

You are given a sequence a consisting of n integers. Find the maximum possible value of  (integer remainder of ai divided by aj), where 1 ≤ i, j ≤ n and ai ≥ aj.

Input: The first line contains integer n — the length of the sequence (1 ≤ n ≤ 2·105). The second line contains n space-separated integers ai (1 ≤ ai ≤ 106).

Output: Print the answer to the problem.


Sample Inputs:
3
3 4 5

Sample Outputs:
2

Solution (Python):
input()
s = sorted(set(map(int, input().split())))
c = m = 0
d = []
for b in s:
    d += [c] * (b - c)
    c = b
for b in s[-1::-1]:
    if b < m + 2:
        break
    m = max(m, c % b, *(a % b for a in d[2 * b - 1::b]))
print(m)

Solution (Python):
input()
s = sorted(set(map(int, input().split())))
c = m = 0
d = []
for b in s:
    d += [c] * (b - c)
    c = b
for b in s[-1::-1]:
    if b < m + 2:
        break
    m = max(m, c % b, *(a % b for a in d[2 * b - 1::b]))
print(m)

Solution (Python):
def main():
    input()
    aa = sorted(set(map(int, input().split())))
    x = []
    b = res = 0
    for a in aa:
        x += [b] * (a - b)
        b = a
    x.append(b)
    maxa = aa.pop()
    for a in reversed(aa):
        if a < res:
            break
        res = max(res, maxa % a, *[b % a for b in x[2 * a - 1::a]])
    print(res)
if __name__ == '__main__':
    main()