Выяснить, можно ли по одному внешнему номеру сделать элементы массива одинаковыми | Набор 2

Опубликовано: 21 Сентября, 2022

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

  1. Добавьте X к элементу массива один раз.
  2. Вычтите X из элемента массива один раз.
  3. Не выполнять никаких операций над элементом массива.

Задача состоит в том, чтобы проверить, существует ли число X такое, что при выполнении вышеуказанных операций с числом X элементы массива становятся равными. Если число существует, выведите «Да» и значение X . В противном случае выведите «Нет» .

Примеры:

Input: arr[] = {2, 3, 3, 4, 2}
Output: Yes 1
Explanation:
Consider the value of X as 1 and increment the array element arr[0](= 2) and arr[4](= 2) by 1, and decrement arr[3](= 4) by 1 modifies the array to {3, 3, 3, 3, 3}.
Therefore, print Yes with the value X as 1.

Input: arr[] = {4, 3, 2, 1}
Output: No

Подход: Данная проблема может быть решена на основе следующих наблюдений:

  • Если все числа равны, ответ « ДА ».
  • Если в массиве есть два различных числа, ответ будет « ДА », так как каждое уникальное число может быть преобразовано в другое целое число после операции.
  • Если в массиве есть как минимум четыре различных числа, ответ будет « НЕТ » из-за свойства сложения.
  • В других случаях, если есть три различных числа A < B < C , то все элементы массива можно сделать равными, увеличив все A на B – A и уменьшив все C на C – A . Следовательно, ответ будет « ДА » только в том случае, если 2*В равно (С+А)/2 .

Выполните следующие шаги, чтобы решить проблему:

  • Инициализируйте 3 переменные, скажем, X, Y и Z как -1 , чтобы сохранить все 3 различных целых числа массива arr[].
  • Пройдите по заданному массиву arr[] с помощью переменной i и выполните следующие шаги:
    • Если какие-либо из X, Y и Z равны -1 , присвойте этой переменной arr[i] .
    • В противном случае, если ни один из X, Y и Z не равен arr[i] , выведите « NO » и вернитесь.
  • Если любой из X, Y и Z равен -1 , то выведите « YES ».
  • Сохраните наименьший элемент в X , следующий по величине элемент в Y и самый большой элемент в Z.
  • Теперь, если ZY равно (Y – X) , то выведите « YES ». В противном случае выведите « НЕТ ».

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

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

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