Минимум замен, необходимых для того, чтобы сумма всех подмассивов длины K была равна

Дан массив arr[] , состоящий из N положительных целых чисел и целого числа K , задача состоит в том, чтобы сделать сумму всех подмассивов длины K равной, заменив минимальное количество элементов массива любым целым числом.

Примеры:

Input: arr[] = {3, 4, 3, 5, 6}, K = 2
Output: 2
Explanation: 
Operation 1: Replacing arr[3] by 4 modifies arr[] to {3, 4, 3, 4, 6}.
Operation 2: Replacing arr[4] by 3 modifies arr[] to {3, 4, 3, 4, 3}.
All subarrays of length 2 are {{3, 4}, {4, 3}, {3, 4}, {4, 3}}. Sum of all these subarrays is 7. Therefore, the minimum number of operations required is 2.

Input: arr[] = {1, 2, 3, 1, 2}, K = 3
Output: 0
Explanation: All subarrays of length 3 are {{1, 2, 3}, {2, 3, 1}, {3, 1, 2}}. Since all these subarrays have sum 6, the number of operations required is 0.

Подход: Идея основана на наблюдении, что все подмассивы будут иметь одинаковую сумму, когда все элементы, разделенные расстоянием K , равны.

Следовательно, задачу можно решить, подсчитав частоту элементов, разделенных расстоянием K , и найти число, которое встречается максимальное количество раз. Выполните следующие шаги, чтобы решить проблему:

• Инициализировать переменную и сохранить требуемый результат.
• Итерация в диапазоне [0, K-1], используя переменная я
  • Создайте карту, freq для хранения частоты элементов, разделенных расстоянием K , начиная с i .
  • Пройдитесь по карте и найдите элемент, который встречается максимальное количество раз.
  • Снова пройтись по карте и если элемент не равен максимальному встречающемуся элементу, добавьте его частоту к ответу .
• Выведите значение ans в качестве результата.

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

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