affix's blog

Greatest GCD between some numbers
By affix, 11 years ago, In English

We've got n nonnegative numbers (a[i]) . We want to find the pair with maximum gcd. For example if we have:

2 4 5 15

gcd(2,4)=2

gcd(2,5)=1

gcd(2,15)=1

gcd(4,5)=1

gcd(4,15)=1

gcd(5,15)=5

The answer is 5.

n<100,000 and a[i]<100,000

I have an O(n*sqrt(n)) algorithm is there more efficient algorithm like O(n*logn) or O(n)?

  • Vote: I like it
  • +7
  • Vote: I do not like it

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

What's the limitation for the numbers itself?

Or we can suppose that a[i] = O(n)?

Otherwise, you can factor all numbers and do something with it. In that case assympotics will include sqrt(max(a[i])) and probably it will be better.

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

    a[i] < 100,000

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

    I can optimize my algorithm to O(max_a[i] * sqrt(max_a[i]) ) but it is not fast enough. I heard there is O (max_a[i] * log(max_a[i])) algorithm! do you have any idea?

    → Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it +15 Vote: I do not like it 
for d = 1..10^5
  for i = 1..10^5/d
    sumCnt += cnt[i * d]
  if (sumCnt >= 2) ans = max(ans, d)
→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Is this algorithm O(n*log(n))?

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

      Yes have a look at http://codeforces.net/blog/entry/8672 [354C — Vasya and Beautiful Arrays]

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

      Yes , because N + N/2 + N/3 + N/4 ... + N/N = O(N log N)

      → Reply
    • »
      »
      »
      11 years ago, # ^ |
      ← Rev. 5   Vote: I like it -8 Vote: I do not like it

      My comment is wrong.

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

        You are wrong. Not all implementations of "sieve of Eratosthenes" require N Log Log N time. Algorithm above is N log N because N + N/2 + N/3 + N/4 ... + N/N = O(N log N)

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

          I'm sorry. "Sieve of Eratosthenes" algorithm use only prime numbers, which are spreaded as O (log (n))

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

    Thanks! It is really n*logn

    → Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I am thinking of a way a little bit strange to solve this problem. You just randomly pick up two numbers and calculate the gcd. Run it 100000 times. Your possibility to get the right answer is very close to 1. Try it out.

→ Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    It is not true. Test case 2 4 1 1 1 .. 1 1 1 (99998 times one). Probatility to choose first and second numbers is 2 / (n * (n — 1)).

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Every time the possibility I didn't choose 2 4 is p, then p = (1 — 2/(n * (n — 1))). So in the end, the possibility that I didn't come up with the right answer is p ^ 100000. I think is close to 0. Is that it?

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

        You can apply your idea in that problem http://codeforces.net/contest/364/problem/D

        Try it out!

        → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
        ← Rev. 3   Vote: I like it 0 Vote: I do not like it

        Not so close. Lets k = n * (n — 1) / 2. p = 1 — 1/k. it's well known equation 1 / e ~ (1 — 1 / k)^k for big k. e = 2.712. ln(e) = 1. So probability to not choose first two numbers is about (1/e)^(2 / (n — 1)) ~ 1 / (1 + 2/(n — 1))

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

          Yeah, you're right. I've noticed that. Thx.

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

      OK, sorry for my idea without test. In fact, p^100000 is about 0.9998....So in this problem, n' scale is 100000, this method didn't work out. However, when n is about 400 or smaller, 100000 times can almost gives a right answer.

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

        When N is so small we could check all possible pairs. I think your idea doesn't work for these kinds of problems.

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

This question is close with HackerRank WoC 34 #2 (https://www.hackerrank.com/contests/w34/challenges/maximum-gcd-and-sum), please don't answer comments like written today and from "fake" accounts till end of competition. However, there is answer in comments...

Good luck

→ Reply