Проверьте, можно ли сделать элементы массива последовательными, выполнив заданные операции.

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

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

  • Оставьте элемент без изменений (arr[i] = arr[i])
  • Увеличить элемент на 1
  • Уменьшить элемент на 1

Примечание. Для каждого элемента массива одну из вышеперечисленных операций можно применить только один раз.

Примеры:

Input: N = 2, arr[] = {2, 4}
Output: YES
Explanation: This array can be converted into {3, 4} or {2, 3}
It is possible to get the consecutive sequence. So the output will be “YES”.

Input: N = 4, arr[] = {1, 2, 3, 7}
Output: NO
Explanation: There is no way to make the elements consecutive using above operations. 
So the output is “NO”.

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

Наблюдения:

There are only three possibilities:  

  • If first element is incremented then the whole sequence should look like arr[0] + 1, arr[0] + 2, arr[0] + 3, and so on
  • If first element is left unchanged then the whole sequence should look like arr[0], arr[0] + 1, arr[0] + 2, arr[0] + 3, and so on.
  • If first element is decremented then the whole sequence should look like arr[0]-1, arr[0], arr[0] + 1, arr[0] + 2, arr[0] + 3, and so on.

If it is possible to convert the given array in any of the above three possibilities then the output will be “YES” else “NO“.

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

  • Создайте три возможных массива в зависимости от того, уменьшается ли первый элемент, увеличивается или остается без изменений.
  • Поочередно проверяйте для каждой возможности, можно ли преобразовать данный массив в возможный массив, изменив значение элемента массива на +1, 0 или -1.
  • Если возможно преобразовать массив в любую из трех форм, тогда ответ «ДА», иначе «НЕТ».

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

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

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