Количество индексов со значением 1 после последовательного выполнения заданных операций

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

Дан двоичный массив a[] размера N и целое число X . Все значения массива равны 0 , кроме индекса X , т.е. a[X] = 1 . Дан другой массив пары v[][] размера M , обозначающий M последовательных операций, выполняемых в массиве. В i -й операции все значения, лежащие в индексах [ v[i][0], v[i][1] ] , заменяются на 1 , если в этом диапазоне была хотя бы одна 1 . Найдите общее количество единиц после последовательного выполнения этих операций.

Примеры:

Input: v[][] = {{1, 6}, {2, 3}, {5, 5}}, N = 6, X = 4
Output: 6
Explanation: Initially the range of elements that can be 1 is [3, 3]. The array is {0, 0, 1, 0, 0, 0}
After the first operation – there is 1 in the given range [1, 6]. So array becomes {1, 1, 1, 1, 1, 1}
After the second operation and third operation the array will be same.
So total number of 1s are 6.

Input: v[][] = {{2, 4}, {1, 2}}, N = 4, X = 1
Output: 2
Explanation: Initially the range of the elements that can be 1 is [1, 1]. The array is {1, 0, 0, 0}.
After the first operation – there is no 1 in [2, 4]. So, the array will be {1, 0, 0, 0}.
After the second operation – there is one 1 in [1, 2]. So, the array will be {1, 1, 0, 0}
So, total number of indices that can have 1 is 2.

Подход: считайте, что текущий диапазон равен [L, R]. Первоначально диапазон [L, R] равен [X, X], потому что изначально только X -я позиция равна 1. Теперь повторите каждый из заданных диапазонов, может быть 2 возможности.

  • The current range [L, R] is intersecting with the ith range, Update the current range [L, R] equals [min(L, b[i][0]), max(b[i][1])).
  • The current range [L, R] is not intersecting with the ith range, no operation will be performed in this case.

Окончательный ответ будет R-L+1. Выполните следующие шаги, чтобы решить проблему:

  • Инициализируйте переменные L и R как X.
  • Переберите диапазон [0, M), используя переменную i , и выполните следующие шаги:
    • Если l меньше, чем равно v[i].second, а R больше, чем равно v[i][0], тогда установите значения L как минимум L или v[i][0] и R как максимум R или v[i][1].
  • После выполнения вышеуказанных шагов выведите значение (R – L + 1) в качестве ответа.

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

Временная сложность: O(M), поскольку мы используем цикл для прохождения M раз, поэтому это будет стоить нам O(M) времени.
Вспомогательное пространство: O(1), так как мы не используем дополнительное пространство.

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