Определите победителя, если игрок удалит любое число 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)
Статьи по Теме:
- Введение в массивы — учебные пособия по структуре данных и алгоритмам
- Теория игры