Количество элементов в массиве A, оставшихся после выполнения операции удаления/поворота на основе заданных условий

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

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

  1. Если начальные элементы массива A[] и B[] равны, то удаляем оба элемента.
  2. В противном случае добавьте начальный символ массива A[] в конец массива A[] после его удаления.

Примеры:

Input: A[] = {1, 1, 0, 1}, B[] = {1, 0, 1, 1}, N = 4 
Output: 0 
Explanation:
The operations are performed as follows:

  1. A[0]( =1) = B[0]( =1): Delete the elements. Thereafter, the arrays are modified to {1, 0, 1} and {0, 1, 1} respectively.
  2. A[0](=1) != B[0](= 0): Shift the A[0] to the end of the array A[]. Thereafter, the arrays are modified to { 0, 1, 1} and {0, 1, 1} respectively.
  3. A[0]( =0) = B[0]( =0): Delete the elements. Thereafter, the arrays are modified to {1, 1} and {1, 1} respectively.
  4. A[0]( =1) = B[0]( =1): Delete the elements. Thereafter, the arrays are modified to {1} and {1} respectively.
  5. A[0]( =1) = B[0]( =1): Delete the elements. Thereafter, both arrays became empty.

Therefore, no elements are left in the array A[].

Input: A[] = {1, 0, 1, 1, 1, 1}, B[] = {1, 1, 0, 1, 0, 1}, N = 6 
Output: 2 

Подход: Данную проблему можно решить, удалив общие 0 и 1, а затем подсчитав уникальное количество 0 и 1 в обоих массивах. Рассмотрим следующие наблюдения:

  1. Элементы могут быть удалены, если в массиве A[ ] остался элемент, равный первому элементу B[ ].
  2. Также можно заметить, что порядок элементов A[] можно легко изменить.
  3. Таким образом, идея состоит в том, чтобы вести подсчет количества нулей и единиц , оставшихся в A[] , и если элемент встречается в B[] таким образом, что этот же элемент больше не присутствует в A[] , то не более операции можно проводить.

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

  • Пройдите массив A[] и подсчитайте общее количество 0 и 1 в переменных и сохраните их в переменных, скажем, ноль и один соответственно.
  • Инициализировать переменную, скажем, считать как 0 для хранения общего количества выполненных удалений.
  • Перейдите массив B[] с помощью переменной i и выполните следующие действия:
    • Если B[i] равно 0 и zero>0 , то увеличиваем значение count на 1 и уменьшаем ноль на 1 .
    • В противном случае, если B[i] равно 1 и one>0 , тогда увеличьте значение count на 1 и уменьшите единицу на 1 .
    • В противном случае прервите цикл, так как дальнейшие операции не могут быть выполнены.
  • Наконец, после выполнения вышеуказанных шагов выведите разницу между N и count в качестве результата.

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

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

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