PROBLEM LINK
DIFFICULTY
SIMPLE
PREREQUISITES
Simple Math
PROBLEM
You are given a list of numbers. You have to find the smalelst number which divides all these numbers.
QUICK EXPLANATION
To the initiated, this question should be a breeze.
- Find the GCD of the list of numbers.
- Find the smallest prime factor of the GCD.
EXPLANATION
The GCD of two numbers can be found using the Euclid’s Algorithm.
gcd(a,b)
return (b == 0) ?
a : gcd(b, (a mod b))
The GCD of a list of numbers A[1 … N] can be found as
let G = 0
for i = 1 to N
G = gcd( A[i], G )
The above is intuitive and easy to prove by induction.
Now, the next step is to find the smallest prime factor of the GCD. Calculating this can be done in O(sqrt(N)) time easily.
for i = 2 to floor(sqrt(G))
if G is divisible by i
return i
return G // Since G is prime!
This calculation is probably the most time consuming step in the solution. Although, iterating till sqrt(G) will fit within the time limit, you can make one optimization to make it faster. That optimization is pre-calculation! You can pre-calculate the smallest primes in the factorization of any number by sieving.
Consider the snippet below
smallestPrime[ 2 ... N ] // We will store our answers here
for i = 2 to N
smallestPrime[i] = i
for i = 2 to N
if smallestPrime[i] = i
for j = 2*i to N, step-size i
smallestPrime[j] = min( smallestPrime[j], i )
Notice how we modify the step in which in the usual Sieve of Eratosthenes, we set the multiples of i as non-prime. In this step now, we are simply updating the smallestPrime array at index j. This is a very clever trick to master while solving problems. When you deal with a problem where you need to perform an operation based on all prime factors of a number (like in this case, we wanted to find the smallest of them), a small code snippet like above is usually needed.
SETTERS SOLUTION
Can be found here.
TESTERS SOLUTION
Can be found here.
