Modified GCD of an array

Правка en6, от NiteshSharma5, 2020-05-20 06:13:29

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.

Теги #number theory, #probabilities

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en6 Английский NiteshSharma5 2020-05-20 06:13:29 2 Tiny change: ' at least 3 numbers o' -> ' at least 4 numbers o'
en5 Английский NiteshSharma5 2020-05-19 19:34:46 0 (published)
en4 Английский NiteshSharma5 2020-05-19 19:33:55 4
en3 Английский NiteshSharma5 2020-05-19 19:32:58 18
en2 Английский NiteshSharma5 2020-05-19 19:30:41 102
en1 Английский NiteshSharma5 2020-05-19 19:26:53 851 Initial revision (saved to drafts)