AC - GCD On Blackboard

Solution

The problem asks us to find the maximum possible GCD of the remaining $N-1$ numbers after taking any one of them away. Naively trying every single combination will result in a complexity of $\mathcal{O}(N^2 + N \log(\max a_i))$ as there are $N$ different ways to take away a number and calculating the GCD will take $\mathcal{O}(N+\log(\max a_i))$ time per case.

To speed this process up, we can calculate the GCDs of every prefix and suffix. Let $l[i] = \gcd_{j=1}^{i} a[j]$ and $r[i] = \gcd_{j=i}^{N} a[j]$. Then the answer is the maximum of $\gcd(l[i-1],r[i+1]),$ $i \in [1,N]$.

Time Complexity: $\mathcal{O}(N+\log(\max a_i))$

Implementation

Copy
#include <bits/stdc++.h>
using namespace std;

const int maxN = 1e5 + 5;

int arr[maxN];
int prefGcd[maxN];  // prefGcd[i] = GCD of a1,a2, ..., ai
int suffGcd[maxN];  // suffGcd[i] = GCD of ai, ai+1, ..., an
int N;

Copy
from math import gcd

n = int(input())
arr = list(map(int, input().split()))

ans = 0

prefix_gcd = [0] * n
prefix_gcd[0] = arr[0]

Copy
import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) throws IOException {
		Kattio io = new Kattio();
		int n = io.nextInt();
		int[] a = new int[n];

		for (int i = 0; i < n; i++) { a[i] = io.nextInt(); }