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)