Найти НОД наиболее часто встречающихся и наименее встречающихся элементов данного массива

Опубликовано: 20 Сентября, 2022

Учитывая массив arr[] размера n , задача состоит в том, чтобы найти GCD элемента с самой высокой и самой низкой частотой в данном массиве.

Примеры:

Input: arr[] = {2, 2, 4, 4, 5, 5, 6, 6, 6, 6}
Output: 2
Explanation: The frequency of the elements in the above array is 
freq(2) = 2, 
freq(4) = 2, 
freq(5) = 2, 
freq(6) = 4, 
The minimum frequency is 2 (of elements 2, 4, and 5). So 2 will be picked as the least among 2, 4, and 5. 
The largest frequency is 4 (of element 6). 
Hence GCD of 2 and 6 = gcd(2, 6) is 2.

Input: arr[] = {3, 2, 2, 44, 44, 44, 44}
Output: 1

Подход: Идея состоит в том, чтобы подсчитать частоты всех элементов и сохранить их в векторе, а затем найти НОД наиболее часто встречающихся и наименее встречающихся элементов.

Ниже приведена реализация вышеуказанного подхода:


Временная сложность: O (n * log (n))
Вспомогательное пространство: O(n)

РЕКОМЕНДУЕМЫЕ СТАТЬИ