xennygrimmato's blog

By xennygrimmato, 7 years ago, In English

Q: Given an array of n integers, find the maximum value of GCD for all possible pairs.

Sample Test Case- 1 2 3 4 5 Output: 2

2<=n<=10^5

Tags gcd
 
 
 
 
  • Vote: I like it
  • +3
  • Vote: I do not like it

»
7 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Take a look at this post.

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

Mark all divisors of each element, in O(sqrt(n)). Then find maximum element of mark array that is marked more than twice, in O(n).

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

    Please explain more. I don't understand anything.

    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      for(int i=0;i<n;i++) { for(int j=1;j*j<=a[i];j++) { if(a[i]%j==0) { mark[j]++; mark[a[i]/j]++; } } } complexity is O(N*SQRT(MAX(A)))

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

        I understood. Thank you.

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it -24 Vote: I do not like it

        Hey its really urgent thanks to your post that i could get max gcd of all pairs so fast but i really also need to know for which such pair is it the max wrt your solution how do i calculate which pair it is ?? Please help and reply asap

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I solved a cses problem using this method but got TLE for some cases. I need more efficient or some modification over this.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it -34 Vote: I do not like it

    Hey its really urgent thanks to your post that i could get max gcd of all pairs so fast but i really also need to know for which such pair is it the max wrt your solution how do i calculate which pair it is ?? Please help and reply asap

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

If you are referring to the problem from the yesterday contest on CodeChef, I got AC in O(MaxA * log(MaxA)) by trying all possible GCDs and seeing if there are at least two numbers that divide it, same as mentioned in the post (link given in the first comment). However, it required some optimization to actually fit it into the TL (Like clearing the array of used digits in O(N) rather than in O(MaxA).). I wonder if there is a solution that doesn't depend on the values of numbers and is fast enough.

»
3 years ago, # |
  Vote: I like it +11 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

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

    For the next week, not just for today :)

  • »
    »
    3 years ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    Oh really?! Obviously you got that. I'm no way trying to get the code. I had doubt that's it. Thanks a lot.Whatever, I'll figure it out.