Найдите X, чтобы большинство элементов массива имели форму (X + p*K)

Учитывая массив arr[] и число K , задача состоит в том, чтобы найти значение X такое, что максимальное количество элементов массива может быть выражено в форме (X + p*K).

Примечание. Если возможных значений X несколько, выведите минимальное из них.

Примеры:

Input: arr[] = {1, 3, 5, 2, 4, 6}, k = 2
Output: 1
Explanation: On choosing 1 the elements of the form 1 + 2* p are 1, 3, 5 so 3 which is the maximum count of elements of the given form and 1 is the minimum number satisfying the condition, thus the output will be 1.

Input : arr[] = {4, 10, 50}, k = 100
Output: 4
Explanation: On choosing any number we get only that number possible of that form at p = 0 so answer is minimum of the array thus 4 will be the output.

Подход: Это можно решить, используя следующую идею.

Since a number X from is to be chosen such that the most elements in the array should be of the form y = X + p * K, where K is a constant, so we can see that X is the remainder when y is divided by K.

So the number that is going to be chosen should be the remainder that is occurring maximum times when array elements are divided by K.

Выполните шаги, указанные ниже, чтобы решить проблему:

• Инициализируйте хэш-карту m для хранения частот остатков.
• Инициализируйте res = INT_MAX , чтобы сохранить выбранное число.
• Инициализируйте max_rem для хранения максимальной частоты остатков при делении на K .
• Пройдите через массив и вычислите остаток при делении на K и сохраните частоту в хэш-карте m .
• Сохраните максимальную частоту остатков в переменной max_rem .
• Теперь пройдитесь по массиву и выберите минимальное количество элементов с одинаковой частотой остатков.
• Верните разрешение .

Ниже приведена реализация описанного выше подхода.

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