Минимизируйте различные элементы в массиве после замены arr[i] на arr[i] по модулю X

Опубликовано: 25 Февраля, 2023

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

  • Выберите целое число X и замените каждый элемент массива остатком, когда arr[i] делится на X (т. е. arr[i]%X).

Примеры:

Input: N = 5, arr[] = {5, 10, 20, 35, 15}
Output: 1
Explanation: Lets take X = 5. On replacing each element 
as mentioned above we get arr = {0, 0, 0, 0, 0}. 
Now this array has only one distinct element (0).

Input: N = 4, arr[] = {1, 4, 8}
Output: 2

Подход: Чтобы решить проблему, следуйте следующему наблюдению:

The answer would be at – most 2. 

This would be the case when we choose X = 2. The final array will contain only either 0 (for even numbers) or 1 (for odd numbers). 

So, now the task is to check for the condition when the answer would be 1.

We want to find X, such that A[1] % X = A[2] % X, A[2] % X = A[3] % X, and so on for the whole array.
Therefore, (A[1] – A[2]) % X = 0 and (A[2] – A[3]) % X = 0 and so on for the whole array.
Therefore, we need to find an X, such that all the consecutive differences are divisible by it. 

Итак, для решения проблемы можно предпринять следующие шаги:

  • Инициализировать переменную gcd на 0.
  • Перебрать массив от 0 до N-1.
    • На каждой итерации брать gcd переменной gcd и разница между arr[i] и arr[i + 1].
  • В конце итерации, если gcd равен 1, вернуть 2.
  • В противном случае верните 1.

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

Временная сложность: O (N * log (M)), где M — максимальное значение массива.
Вспомогательное пространство: O(1)

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