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

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

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

  • Для любого индекса i, 0 < i < N, сделайте A[i] = A[i] – A[i-1]

Напечатайте «YES» или «NO» соответственно.

Примеры:

Input: N = 2, A[] = {2, 8, 4}
Output:YES.
Explanation: Choose i = 1, the array becomes {2, 6, 4}
Choose i = 1, the array becomes {2, 4, 4}
Choose i = 2, the array becomes {2, 4, 0}
Choose i = 1, the array becomes {2, 2, 0}
Choose i = 1, the array becomes {2, 0, 0}

Input: N = 2, A[] = {3, 4, 2}
Output: NO

Подход:

If first element of the array is a factor of all the remaining elements of the array, then the elements of array can be made 0, because any of them can be converted to have the value same as the first elements. Otherwise, it is not possible.

Следуйте данному шагу, чтобы реализовать данную идею:

  • Запустите цикл от i = 1 до N-1 .
  • Проверьте, имеет ли каждый элемент коэффициент , равный первому элементу.
  • Если все элементы массива имеют коэффициент, равный первому элементу, выведите YES .
  • В противном случае выведите НЕТ .

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

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

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