跳转至

810.chalkboard-xor-game

Statement

Metadata
  • Link: 黑板异或游戏
  • Difficulty: Hard
  • Tag: 位运算 脑筋急转弯 数组 数学 博弈

黑板上写着一个非负整数数组 nums[i] 。

Alice 和 Bob 轮流从黑板上擦掉一个数字，Alice 先手。如果擦除一个数字后，剩余的所有数字按位异或运算得出的结果等于 0 的话，当前玩家游戏失败。 另外，如果只剩一个数字，按位异或运算得到它本身；如果无数字剩余，按位异或运算结果为 0。

并且，轮到某个玩家时，如果当前黑板上所有数字按位异或运算结果等于 0 ，这个玩家获胜。

假设两个玩家每步都使用最优解，当且仅当 Alice 获胜时返回 true。

 

示例 1：

输入: nums = [1,1,2]
输出: false
解释: 
Alice 有两个选择: 擦掉数字 1 或 2。
如果擦掉 1, 数组变成 [1, 2]。剩余数字按位异或得到 1 XOR 2 = 3。那么 Bob 可以擦掉任意数字，因为 Alice 会成为擦掉最后一个数字的人，她总是会输。
如果 Alice 擦掉 2，那么数组变成[1, 1]。剩余数字按位异或得到 1 XOR 1 = 0。Alice 仍然会输掉游戏。

示例 2:

输入: nums = [0,1]
输出: true

示例 3:

输入: nums = [1,2,3]
输出: true

 

提示：

  • 1 <= nums.length <= 1000
  • 0 <= nums[i] < 216

Metadata
  • Link: Chalkboard XOR Game
  • Difficulty: Hard
  • Tag: Bit Manipulation Brainteaser Array Math Game Theory

You are given an array of integers nums represents the numbers written on a chalkboard.

Alice and Bob take turns erasing exactly one number from the chalkboard, with Alice starting first. If erasing a number causes the bitwise XOR of all the elements of the chalkboard to become 0, then that player loses. The bitwise XOR of one element is that element itself, and the bitwise XOR of no elements is 0.

Also, if any player starts their turn with the bitwise XOR of all the elements of the chalkboard equal to 0, then that player wins.

Return true if and only if Alice wins the game, assuming both players play optimally.

 

Example 1:

Input: nums = [1,1,2]
Output: false
Explanation: 
Alice has two choices: erase 1 or erase 2. 
If she erases 1, the nums array becomes [1, 2]. The bitwise XOR of all the elements of the chalkboard is 1 XOR 2 = 3. Now Bob can remove any element he wants, because Alice will be the one to erase the last element and she will lose. 
If Alice erases 2 first, now nums become [1, 1]. The bitwise XOR of all the elements of the chalkboard is 1 XOR 1 = 0. Alice will lose.

Example 2:

Input: nums = [0,1]
Output: true

Example 3:

Input: nums = [1,2,3]
Output: true

 

Constraints:

  • 1 <= nums.length <= 1000
  • 0 <= nums[i] < 216

Solution

from functools import reduce
from typing import List


class Solution:
    def xorGame(self, nums: List[int]) -> bool:
        xorSum = reduce(lambda x, y: x ^ y, nums)
        l = len(nums)
        return xorSum == 0 or (l & 1) == 0
最后更新: October 11, 2023
回到页面顶部