ScienceGuy's blog

Maximum of GCD of N numbers
By ScienceGuy, history, 7 years ago, In English

What is the efficient algorithm to find the maximum Greatest Common Divisor of N numbers? Input: First line contains N (2<=N<=10^5). Next line contains N numbers, each of them more than 1 and less than 10^5, output: Output the largest GCD of any pair of numbers.

  • Vote: I like it
  • -2
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
7 years ago, # |
  Vote: I like it +7 Vote: I do not like it

https://www.hackerrank.com/contests/w34/challenges/maximum-gcd-and-sum

Come on dude. Cant wait 10 hours more?

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Assign v, v[x] = 1 if there was a number divisible by x. Go with i through the array. Find all divisors of a[i], for each divisor x, if v[x] = 1 update maximum with x. Solution O(N^1.5).

→ Reply
»
7 years ago, # |
  Vote: I like it +1 Vote: I do not like it

You can iterate over all possible gcds and for each check if there exist two or more numbers divisable by it (and if there are, choose two largest).

If you do it in way like this:

for (int gcd = 1; gcd < m; gcd++) {

for (int i = gcd; i < m; i += gcd) {

...

it will work in O(m log m) because m/1 + m/2 + m/3 + ... + 1/m = m * (1/1 + 1/2 + 1/3 + ... + 1/m) = m * O(log m) = O(m log m)

→ Reply