Минимум операций, необходимых для того, чтобы все элементы массива делились на K
Дан массив a [] , целое число K и целое число X (которое изначально инициализировано равным 0). Наша задача - найти минимальное количество ходов, необходимых для обновления массива, чтобы каждый его элемент делился на K, выполнив следующие операции:
- Выберите один индекс i от 1 до N и увеличьте i на X, а затем увеличьте X на 1. Эту операцию нельзя применять более одного раза к каждому элементу массива.
- Увеличьте значение X только на 1.
Примеры:
Input: K = 3, a = [1, 2, 2, 18]
Output: 5
Explanation:
Initially X = 0 hence update X to 1.
For X = 1 add X to the second element of array to make the array [1, 3, 2, 18] and increase X by 1.
For X = 2 add X to the first element of array [3, 3, 2, 18] and increase X by 1.
For X = 3 just increase X by 1.
For X = 4 add X to the third element of array to make the array [3, 3, 6, 18] and increase X by 1.
At last, the array becomes [3, 3, 6, 18] where all the elements are divisible by K = 3.
Input: K = 5, a[] = [15, 25, 5, 10, 20, 1005, 70, 80, 90, 100]
Output: 0
Explanation:
Here all elements are already divisible by 5.
Подход: основная идея состоит в том, чтобы найти максимальное значение X, необходимое для обновления элементов массива, чтобы он делился на K.
- Для этого нам нужно найти максимальное значение (K - (a i mod K)), которое нужно добавить к элементам массива, чтобы оно делилось на K.
- Однако могут быть равные элементы, поэтому отслеживайте количество таких элементов, используя структуры данных карты.
- Когда в массиве найден другой такой элемент, обновите ответ с помощью (K - (a i mod K)) + (K * количество равных элементов), потому что с каждым ходом мы увеличиваем X на 1.
Ниже представлена реализация описанного выше подхода:
Сложность времени: O (N)
Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по доступной для студентов цене и будьте готовы к работе в отрасли. Получите все важные математические концепции для соревновательного программирования с курсом Essential Maths for CP по доступной для студентов цене.
Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.