Hackerrank Solution: Easy GCD

Original Problem

We call a sequence of $n$ non-negative integers, $A$, awesome if there exists some positive integer $x>1$ such that each element $a_i$ in $A$ (where $0\leq i<n$) is evenly divisible by $x$. Recall that $a$ evenly divides $b$ if there exists some integer $c$ such that $b=a\cdot c$.

Given an awesome sequence, $A$, and a positive integer, $k$, find and print the maximum integer, $l$, satisfying the following conditions:

1. $0\leq l \leq k$
2. $A\cup \{l\}$ is also awesome

Input Format

The first line contains two space-separated positive integers, $n$ (the length of sequence $A$) and $k$ (the upper bound on answer $l$), respectively.

The second line contains $n$ space-separated positive integers describing the respective elements in sequence $A$ (i.e., $a_0, a_1, \dots, a_{n-1}$).

Constraints

• $1\leq n\leq 10^5$
• $1\leq k\leq 10^9$
• $1\leq a_i\leq 10^9$

Output Format

Print a single, non-negative integer denoting the value of $l$ (i.e., the maximum integer $\leq k$ such that $A\cup \{l\}$ is awesome). As $0$ is evenly divisible by any $x>1$, the answer will always exist.

Solution

Given $x>1$ the problem statement defines

$$A\text{ is awesome} \Leftrightarrow x | a_i\forall a_i\in A$$

We now get an awesome list $A$, which says they have a common $x$. The largest $x$ is the GCD of the entire list, which can be determined in Ruby with

x = A.reduce(:gcd)

We're now looking for the largest $l\leq k$ for which also an $x'$ exists that divides all $a_i$ as well as our $l$.

This $l$ should be the greatest under the given constraint. In order to maximize $l$, the idea is to take the smallest prime of $x$ (which we know divides all $a_i$ already) and make it the new common $x'$. Bringing in the new common $x'$ into $l$ is then pretty straightforward:

$$l = x'\left\lfloor\frac{k}{x'}\right\rfloor$$

Finding $x'$ which we said should be the smallest prime of the GCD can be done with this little $O(\sqrt{n})$ helper function:

def smallestPrime(n)
  i = 2
  while i * i <= n do
    return i if n % i == 0
    i+= 1
  end
  return n
end

The solution is thus

k = gets.strip.split.map(&:to_i)[1]
A = gets.strip.split.map(&:to_i)

x = A.reduce(:gcd)
x_= smallestPrime(x)

puts(x_ * (k / x_).floor)