Блог пользователя affix

Greatest GCD between some numbers
Автор affix, 10 лет назад, По-английски

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)?

  • Проголосовать: нравится
  • +7
  • Проголосовать: не нравится

»
10 лет назад, # |
  Проголосовать: нравится -7 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    a[i] < 100,000

    → Ответить
  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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?

    → Ответить
»
10 лет назад, # |
← Rev. 2   Проголосовать: нравится +15 Проголосовать: не нравится 
for d = 1..10^5
  for i = 1..10^5/d
    sumCnt += cnt[i * d]
  if (sumCnt >= 2) ans = max(ans, d)
→ Ответить
»
10 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    10 лет назад, # ^ |
    ← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    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)).

    → Ответить
    • »
      »
      »
      10 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      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?

      → Ответить
    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      → Ответить
      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        → Ответить
»
7 лет назад, # |
  Проголосовать: нравится +17 Проголосовать: не нравится

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

→ Ответить