Определите победителя, если игрок удалит любое число 0 с одной стороны от 1

Учитывая arr[] двоичных цифр. Предположим, что два игрока X и Y играют в игру, в которой за один ход игрок может удалить любое количество нулей слева или справа от элемента 1. Игрок проигрывает игру, если он не может сделать ни одного хода. Задача состоит в том, чтобы найти победителя игры, если оба игрока играют оптимально и Y начинает первым.

Примеры:

Input: arr[] = {1}
Output: X
Explanation: There are no zeros initially in the arr[], Therefore, player Y can’t make any move. Hence, Player X wins the game.

Input: arr[] = {0, 1, 0, 0, 1, 1, 0 }
Output: Y 
Explanation:
Y chose 1 at index 5 along which the game will be played as marked as bold in all below operations, Then:   
Player Y removes 2 zeros from the left side of element 1. Then arr[] = {0, 1, 1, 1, 0 }
player X removes 1 zero from the left side of element 1. Then arr[] = {1, 1, 1, 0 }
Player Y removes 1 zero from the right side of element 1. Then arr[] = {1, 1, 1}
Now, It’s impossible to make any move for player X, because no zeros are present there. Hence player Y wins.

Подход: Реализуйте идею ниже, чтобы решить проблему:

There’s always a winning state present for Y, if zeros at right or left of those 1 are not equal. So this problem can be solved by Counting a number of zeros present left and right of each element 1 present in arr[], Y will choose that 1 optimally at which a number of zeros right or left to that 1 are not equal. If the number of zeros on the left and right side are equal, Then X wins else Y wins.

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

• Инициализируйте две переменные counter1 = 0 и counter2 = 0 для первоначального хранения количества нулей в arr[] и для подсчета нулей слева и справа от единиц в массиве.
• Сохраните количество нулей в переменной counter1 путем обхода arr[] с самого начала .
• Повторите весь массив снова справа:
  • Если текущий элемент равен нулю, то увеличивается counter2 .
  • Если текущий элемент равен единице, проверьте, равен ли counter2 (counter1-counter2) .
    • Если да, верните true. В противном случае вернуть ложь.

Ниже приведена реализация описанного выше подхода.

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

Статьи по Теме:

• Введение в массивы — учебные пособия по структуре данных и алгоритмам
• Теория игры