Максимизируйте частоту элемента, добавив X в подпоследовательность

Учитывая массив A[] размера N , задача состоит в том, чтобы максимизировать частоту любого элемента, добавляя любое положительное целое число X ко всем элементам любой подпоследовательности этого массива. Выведите максимальную частоту, которая может быть достигнута, и значение X. Если X имеет более одного значения, верните любое из них.

Пример:

Input: A[] = {2, 1, 3, 3, 4, 5}
Output: X = 2, Maximum Frequency Possible = 3
Explanation: Convert 1 to 3 to get A[] = {3, 1, 3, 3, 4, 5},  
Here maximum frequency = 3, and we added 2 to each element of the subsequence {1}.

Input: A[] = {5, 6, 4, 5, 5, 4, 7}
Output: X = 1, Maximum Frequency Possible = 5

Подход:

The idea behind this problem is to take the subsequence from array containing only the second most frequent element in the array and convert all the elements to the most frequent element in the array.

Следуйте инструкциям, чтобы решить эту проблему:

• Найдите и сохраните частоту каждого элемента в массиве, используя unordered_map.
• На карте частот найдите элементы с самой высокой и второй по величине частотой в массиве.
• X = абсолютная разница между самым частым и вторым по частоте элементом.
• Максимально возможная частота будет суммой самой высокой и второй по величине частоты.

Ниже приведена реализация этого подхода:

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