Maximum Value (Codeforces 485D)
Tags: Others, binary search

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):
from sys import stdin, stdout
from bisect import bisect_left, bisect
(input, print) = (stdin.readline, stdout.write)
n = int(input())
x = list(map(int, input().split()))
a = [False for i in range(int(1000000.0) + 5)]
for i in x:
    a[i] = True
for i in range(1, int(1000000.0) + 5):
    if a[i]:
        a[i] = i
    else:
        a[i] = a[i - 1]
m = 2 * a[-1]
ans = 0
for j in range(1, int(1000000.0) + 5):
    if a[j] < j:
        continue
    for x in range(2 * j, int(1000000.0) + 5 * j + 1, j):
        y = a[min(x, int(1000000.0) + 1) - 1]
        if y > j:
            ans = max(ans, y % j)
print(str(ans) + '\n')

Solution (Python):
n = int(input())
x = list(map(int, input().split()))
a = [False for i in range(int(1000000.0) + 5)]
for i in x:
    a[i] = True
for i in range(1, int(1000000.0) + 5):
    if a[i]:
        a[i] = i
    else:
        a[i] = a[i - 1]
m = 2 * a[-1]
ans = 0
for j in range(1, int(1000000.0) + 5):
    if a[j] < j:
        continue
    for x in range(2 * j, int(1000000.0) + 5 * j + 1, j):
        y = a[min(x, int(1000000.0) + 1) - 1]
        if y > j:
            ans = max(ans, y % j)
print(ans)

Solution (Python):
from sys import stdin, stdout
from bisect import bisect_left, bisect
(input, print) = (stdin.readline, stdout.write)
n = int(input())
x = list(map(int, input().split()))
a = [False for i in range(int(1000000.0) + 5)]
for i in x:
    a[i] = True
for i in range(1, int(1000000.0) + 5):
    if a[i]:
        a[i] = i
    else:
        a[i] = a[i - 1]
m = 2 * a[-1]
ans = 0
for j in range(1, int(1000000.0) + 5):
    if a[j] < j:
        continue
    for x in range(2 * j, int(1000000.0) + 5 * j + 1, j):
        y = a[min(x, int(1000000.0) + 1) - 1]
        if y > j:
            ans = max(ans, y % j)
print(str(ans) + '\n')