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)

« Back to problem overview