NiteshSharma5's blog

By NiteshSharma5, history, 11 days ago, In English,

Recently I found one amazing problem on Hackerearth that seems to be difficult to be solved within time limits.

we are given an array A of n positive integers and we are supposed to calculate MGCD(k) of A. Here MGCD(k) is the Modified GCD of Order K for an Array A.

Modified GCD of Order K for an array is the Maximum number that divides at least ceil(n/k) number of elements of the array.For example Modified Gcd of Order 2 for array A is the Maximum number that divides at least half of its elements. For example-given n=10, k=3 and array A={24 18 28 8 25 1 48 27 56 16}

In the above example 8 divides 5 elements of the array(24,8,48,56,16) ,which is greater than(>=) ceil(10/3) i.e.=4 There is no number greater 8 than that divides at least 4 numbers of the array.So 8 is the required answer.

Can someone suggest any O(n) or O(nlogn) solution to this problem.

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

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it
  • »
    »
    10 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    yes exactly but I am not able to digest the solution provided there in the editorial

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

If a number $$$d$$$ divides a number $$$n$$$, then any of its prime factors will do as well. So why not factorize every number in the array and store how many elements each primes divides by using a map?

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    but factorization itself will take square root of A[i] time where A[i] i.e. the elements are of order 10^12 and that will lead to TLE beauuse at the same time we have to process n=10^5. So we need to do look for an algorithm that runs in O(n).Help if someone gets the logic

    • »
      »
      »
      8 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Indeed.

      Just like the editorial says, since K is very small, we can use a randomized solution. Pick an element, factorize it and check if divisors divide required number of elements.

      Keep the maximum element you find.

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

        ya You are right I think that is the only possible solution to this problem. But I came here in hope of some other possible solution!!