We are given non-negative integers nums[i] which are 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.  (Also, we'll say 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:
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 becomes [1, 1]. The bitwise XOR of all the elements of the chalkboard is 1 XOR 1 = 0. Alice will lose.



Notes: 


       1 <= N <= 1000. 
       0 <= nums[i] <= 2^16.

Difficulty: interview

Starter code:

class Solution:
    def xorGame(self, nums: List[int]) -> bool:


Solutions:
class Solution:
     def validTicTacToe(self, board):
         """
         :type board: List[str]
         :rtype: bool
         """
         def win(board,w):
             for i in range(3):
                 if board[i] == w*3:
                     return True
             for i in range(3):
                 if board[0][i] == w and board[1][i] == w and board[2][i] == w:
                     return True
             sign = True
             for i in range(3):
                 if board[i][i] != w:
                     sign = False
             if sign:
                 return True
             
             sign = True
             for i in range(3):
                 if board[i][2-i] != w:
                     sign = False
             if sign:
                 return True
         
         Xnum = 0
         Onum = 0
         for ss in board:
             for s in ss:
                 if s == 'X':
                     Xnum += 1
                 if s == 'O':
                     Onum += 1
         if win(board,'X'):
             if Xnum == Onum + 1:
                 return True
             else:
                 return False
         if win(board,"O"):
             if Xnum == Onum:
                 return True
             else:
                 return False
         if Xnum == Onum or Xnum == Onum + 1:
             return True
         else:
             return False


class Solution:
     def validTicTacToe(self, board):
         """
         :type board: List[str]
         :rtype: bool
         """
         xoDict = {"X":[],"O":[]," ":[]}
         
         for i in range(0, 3):
             for j in range(0,3):
                 if board[i][j] == "X":
                     xoDict["X"] += [i,j],
                 elif board[i][j] == "O":
                     xoDict["O"] += [i,j],
                 elif board[i][j] == " ":
                     xoDict[" "] += [i,j],
                     
         if len(xoDict["O"])>len(xoDict["X"]):
             return False
         
         if len(xoDict["X"]) - len(xoDict["O"]) >1:
             return False
         
         xwin = self.check(board, "X")
         owin = self.check(board, "O")
         
         if xwin and owin:
             return False
         
         if xwin and len(xoDict["X"]) == len(xoDict["O"]):
             return False
         if owin and len(xoDict["X"]) > len(xoDict["O"]):
             return False
         
         return True
     
     def check(self, board, char):
         for i in range(0,3):
             if board[i][0] == char and board[i][1] ==char and board[i][2] == char:
                 return True
             
         for i in range(0,3):
             if board[0][i] == char and board[1][i] ==char and board[2][i] == char:
                 return True
             
         if board[0][0] == char and board[1][1] ==char and board[2][2] == char:
             return True
         
         if board[0][2] == char and board[1][1] ==char and board[2][0] == char:
             return True
         
         return False
         
     
     
                     
         


class Solution:
     def validTicTacToe(self, board):
         """
         :type board: List[str]
         :rtype: bool
         """
         cross = 0
         circle = 0
         for i in range(3):
             for j in range(3):
                 if board[i][j] == 'X':
                     cross += 1
                 if board[i][j] == 'O':
                     circle += 1
         if cross < circle or cross - circle > 1:
             return False
         cross_winning = 0
         circle_winning = 0
         for i in range(3):
             if board[i][0] == board[i][1] == board[i][2]:
                 if board[i][0] == 'X':
                     cross_winning += 1
                 elif board[i][0] == 'O':
                     circle_winning += 1
             if board[0][i] == board[1][i] == board[2][i]:
                 if board[0][i] == 'X':
                     cross_winning += 1
                 elif board[0][i] == 'O':
                     circle_winning += 1
         if board[0][0] == board[1][1] == board[2][2]:
             if board[0][0] == 'X':
                 cross_winning += 1
             elif board[0][0] == 'O':
                 circle_winning += 1
         if board[0][2] == board[1][1] == board[2][0]:
             if board[0][2] == 'X':
                 cross_winning += 1
             elif board[0][2] == 'O':
                 circle_winning += 1
                 
         if cross_winning > 0 and circle_winning > 0:
             return False
         if cross_winning > 0 and cross <= circle:
             return False
         if circle_winning > 0 and circle < cross:
             return False
         return True

class Solution:
     def validTicTacToe(self, board):
         """
         :type board: List[str]
         :rtype: bool
         """
         num_X = 0
         num_O = 0
         for i in range(3):
             for j in range(3):
                 if board[i][j] == 'X':
                     num_X += 1
                 elif board[i][j] == 'O':
                     num_O += 1
         if num_X <num_O or num_X > num_O + 1:
             return False
         
         def win(board, total_X, total_O):
             for i in range(3):
                 num_X = 0; num_O = 0
                 for j in range(3):
                     if board[i][j] == 'X':
                         num_X += 1
                     elif board[i][j] == 'O':
                         num_O += 1
                 if num_X == 3:
                     return total_X > total_O
                 if num_O == 3:
                     return total_X == total_O
             for j in range(3):
                 num_X = 0; num_O = 0
                 for i in range(3):
                     if board[i][j] == 'X':
                         num_X += 1
                     elif board[i][j] == 'O':
                         num_O += 1
                 if num_X == 3:
                     return total_X > total_O
                 if num_O == 3:
                     return total_X == total_O
             num_X = 0; num_O = 0
             for i in range(3):
                 if board[i][i] == 'X':
                     num_X += 1
                 elif board[i][i] == 'O':
                     num_O += 1
             if num_X == 3:
                 return total_X > total_O
             if num_O == 3:
                 return total_X == total_O
             num_X = 0; num_O = 0
             for i in range(3):
                 if board[i][2-i] == 'X':
                     num_X += 1
                 elif board[i][2-i] == 'O':
                     num_O += 1
             if num_X == 3:
                 return total_X > total_O
             if num_O == 3:
                 return total_X == total_O
             return True
     
         return win(board, num_X, num_O)

class Solution:
     def validTicTacToe(self, board):
         """
         :type board: List[str]
         :rtype: bool
         """
         O, X = 0, 0
         for r in board:
             for c in r:
                 if c == 'O':
                     O += 1
                 elif c == 'X':
                     X += 1
         if O - X > 0:
             return False
         if X - O > 1:
             return False
         if X - O == 0:
             for r in board:
                 if r == 'XXX':
                     return False
             for c in range(2):
                 if board[0][c] == board[1][c] == board[2][c] == 'X':
                     return False
             if board[0][0] == board[1][1] == board[2][2] == 'X':
                 return False
             if board[2][0] == board[1][1] == board[0][2] == 'X':
                 return False
         else:
             for r in board:
                 if r == 'OOO':
                     return False
             for c in range(2):
                 if board[0][c] == board[1][c] == board[2][c] == 'O':
                     return False
             if board[0][0] == board[1][1] == board[2][2] == 'O':
                 return False
             if board[2][0] == board[1][1] == board[0][2] == 'O':
                 return False
         
         return True

class Solution:
     def validTicTacToe(self, board):
         """
         :type board: List[str]
         :rtype: bool
         """
         O, X = 0, 0
         for r in board:
             for c in r:
                 if c == 'O':
                     O += 1
                 elif c == 'X':
                     X += 1
         if O - X > 0:
             return False
         if X - O > 1:
             return False
         for c in range(2):
             if board[0][c] == 'X' and board[1][c] == 'X' and board[2][c] == 'X':
                 return X - O == 1
             if board[c][0] == 'X' and board[c][1] == 'X' and board[c][2] == 'X':
                 return X - O == 1
         if board[0][0] == 'X' and board[1][1] == 'X' and board[2][2] == 'X':
             return X - O == 1
         if board[2][0] == 'X' and board[1][1] == 'X' and board[0][2] == 'X':
             return X - O == 1
         for c in range(2):
             if board[0][c] == 'O' and board[1][c] == 'O' and board[2][c] == 'O':
                 return X - O == 0
             if board[c][0] == 'O' and board[c][1] == 'O' and board[c][2] == 'O':
                 return X - O == 0
         if board[0][0] == 'O' and board[1][1] == 'O' and board[2][2] == 'O':
             return X - O == 0
         if board[2][0] == 'O' and board[1][1] == 'O' and board[0][2] == 'O':
             return X - O == 0
         
         return True

class Solution:
     def validTicTacToe(self, board):
         """
         :type board: List[str]
         :rtype: bool
         """
         targetState = tuple(board)
         
         startingState = ('   ', '   ', '   ')
         
         stateStack = [startingState]
         visited = set()
         
         while len(stateStack) > 0:
             curState = stateStack.pop()
             
             if curState == targetState:
                 return True
                 
             if curState in visited:
                 continue
                 
             visited.add(curState)
             
             # Has a player won, thus ending the game?
             if any(r == 'XXX' for r in curState) or any(r == 'OOO' for r in curState) \
                or any(''.join([curState[i][j] for i in range(3)]) == 'XXX' for j in range(3)) or any(''.join([curState[i][j] for i in range(3)]) == 'OOO' for j in range(3)) \
                or (curState[0][0] == curState[1][1] == curState[2][2] == 'X') \
                or (curState[0][0] == curState[1][1] == curState[2][2] == 'O') \
                or (curState[0][2] == curState[1][1] == curState[2][0] == 'X') \
                or (curState[0][2] == curState[1][1] == curState[2][0] == 'O'):
                continue
             
             # What moves are there that get closer to the target state?
             moves = set()
             for i,row in enumerate(curState):
                 for j,cell in enumerate(row):
                     if cell == ' ' and cell != targetState[i][j]:
                         moves.add((i,j,targetState[i][j]))
                         
             # Can only add X's and O's
             if len(moves) == 0:
                 continue
                 
             # Now detect *valid* moves; whose turn is it? 
             numX = sum(r.count('X') for r in curState)
             numO = sum(r.count('O') for r in curState)
             
             if numX == numO:
                 curTurn = 'X'
             else:
                 curTurn = 'O'
                 
             # Make each valid move
             for i,j,symbol in moves:
                 if symbol != curTurn:
                     continue
                 # Valid move; spawn a new board state
                 newState = [curState[t] for t in range(3)]
                 newState[i] = curState[i][:j] + curTurn + curState[i][j+1:]
                 stateStack.append(tuple(newState))
                 
         return False

class Solution:
     def validTicTacToe(self, board):
         """
         :type board: List[str]
         :rtype: bool
         """
         x_count, o_count = 0, 0
         # Count number of X and O
         for string in board:
             for c in string:
                 if c == "X":
                     x_count += 1
                 if c == "O":
                     o_count += 1
         # If number of X is two more than or less than that of O, return False
         if x_count - o_count >= 2 or x_count - o_count < 0:
             return False
 
         # Check winner, we can only have one winner. To check winner,
         # there are total 8 combinations.
         x_win = 0
         o_win = 0
         if board[0] == 'XXX' or board[1] == 'XXX' or board[2] == 'XXX':
             x_win += 1
         if board[0] == 'OOO' or board[1] == 'OOO' or board[2] == 'OOO':
             o_win += 1
         if board[0][0] + board[1][0] + board[2][0] == 'XXX' or \
                 board[0][1] + board[1][1] + board[2][1] == 'XXX' or \
                 board[0][2] + board[1][2] + board[2][2] == 'XXX':
             x_win += 1
         if board[0][0] + board[1][0] + board[2][0] == 'OOO' or \
                 board[0][1] + board[1][1] + board[2][1] == 'OOO' or \
                 board[0][2] + board[1][2] + board[2][2] == 'OOO':
             o_win += 1
         if board[0][0] + board[1][1] + board[2][2] == 'XXX' or \
                 board[2][0] + board[1][1] + board[0][2] == 'XXX':
             x_win += 1
         if board[0][0] + board[1][1] + board[2][2] == 'OOO' or \
                 board[2][0] + board[1][1] + board[0][2] == 'OOO':
             o_win += 1
 
         if x_win == 1 and o_win == 1:
             return False
         if x_win == 1 and x_count - o_count != 1 or \
             o_win == 1 and o_count != x_count:
             return False
         return True

class Solution:   
     def isWin(self, board, c):
         for i in range(3):  # Row check
             if board[0][i] == c and board[1][i] == c and board[2][i] == c:
                 return True
         for i in range(3):  # Column check
             if board[i][0] == c and board[i][1] == c and board[i][2] == c:
                 return True
         if board[0][0] == c and board[1][1] == c and board[2][2] == c or \
                 board[0][2] == c and board[1][1] == c and board[2][0] == c:  # Diagonal check
             return True
         
         return False
     
     def validTicTacToe(self, board):
         """
         :type board: List[str]
         :rtype: bool
         """               
         o_cnt = 0
         x_cnt = 0
         for i in range(3):
             for j in range(3):
                 x_cnt += 1 if board[i][j] == 'X' else 0
                 o_cnt += 1 if board[i][j] == 'O' else 0
                 
         if o_cnt > x_cnt or x_cnt > o_cnt + 1:
             return False
         #print(o_cnt,x_cnt,self.isWin(board, 'X'))
         if o_cnt == x_cnt and self.isWin(board, 'X') or x_cnt == o_cnt + 1 and self.isWin(board, 'O'):
             return False
         
         
         
         
         return True

class Solution:
     def validTicTacToe(self, board):
         """
         :type board: List[str]
         :rtype: bool
         """
         O, X = 0, 0
         for r in board:
             for c in r:
                 if c == 'O':
                     O += 1
                 elif c == 'X':
                     X += 1
         if O - X > 0:
             return False
         if X - O > 1:
             return False
         for c in range(2):
             if board[0][c] == 'X' and board[1][c] == 'X' and board[2][c] == 'X':
                 return X - O == 1
             if board[c] == 'XXX': #board[c][0] == 'X' and board[c][1] == 'X' and board[c][2] == 'X':
                 return X - O == 1
         if board[0][0] == 'X' and board[1][1] == 'X' and board[2][2] == 'X':
             return X - O == 1
         if board[2][0] == 'X' and board[1][1] == 'X' and board[0][2] == 'X':
             return X - O == 1
         for c in range(2):
             if board[0][c] == 'O' and board[1][c] == 'O' and board[2][c] == 'O':
                 return X - O == 0
             if board[c] == 'OOO': #board[c][0] == 'O' and board[c][1] == 'O' and board[c][2] == 'O':
                 return X - O == 0
         if board[0][0] == 'O' and board[1][1] == 'O' and board[2][2] == 'O':
             return X - O == 0
         if board[2][0] == 'O' and board[1][1] == 'O' and board[0][2] == 'O':
             return X - O == 0
         
         return True

class Solution:
     def validTicTacToe(self, board):
         """
         :type board: List[str]
         :rtype: bool
         """
         def Xwin(board):
             for r in range(2):
                 if board[r] == 'XXX':
                     return 1
                 if board[r] == 'OOO':
                     return -1
                 if board[0][r] == 'X' and board[1][r] == 'X' and board[2][r] == 'X':
                     return 1
                 if board[0][r] == 'O' and board[1][r] == 'O' and board[2][r] == 'O':
                     return -1
             if board[0][0] == 'X' and board[1][1] == 'X' and board[2][2] == 'X':
                 return 1
             if board[2][0] == 'X' and board[1][1] == 'X' and board[0][2] == 'X':
                 return 1
             if board[0][0] == 'O' and board[1][1] == 'O' and board[2][2] == 'O':
                 return -1
             if board[2][0] == 'O' and board[1][1] == 'O' and board[0][2] == 'O':
                 return -1
             return 0
         O, X = 0, 0
         for r in board:
             for c in r:
                 if c == 'O':
                     O += 1
                 elif c == 'X':
                     X += 1
         if O - X > 0:
             return False
         if X - O > 1:
             return False
         winner = Xwin(board)
         if winner == 1:
             return True if X - O == 1 else False
         elif winner == -1:
             return True if X - O == 0 else False
         return True

class Solution:
     def validTicTacToe(self, board):
         """
         :type board: List[str]
         :rtype: bool
         """
         x = 0
         o = 0
         win_o = 0
         win_x = 0
         for i in range(3):
             for j in range(3):
                 if board[i][j] == 'X':
                     x += 1
                 elif board[i][j] == 'O':
                     o += 1
             if board[i] == 'XXX': 
                 win_x += 1 
             elif board[i] == 'OOO': 
                 win_o += 1
             if board[0][i] == board[1][i] == board[2][i]:
                 if board[0][i] == 'X':
                     win_x += 1
                 elif board[0][i] == 'O':
                     win_o += 1
 
         if board[0][0] == board[1][1] == board[2][2]:
             if board[0][0] == 'O':
                 win_o += 1
             elif board[0][0] == 'X':
                 win_x += 1
         if board[2][0] == board[1][1] == board[0][2]:
             if board[2][0] == 'O':
                 win_o += 1
             elif board[2][0] == 'X':
                 win_x += 1
 
         if x > (o + 1) or x < o or (win_o > 0 and win_x > 0):
             return False
         
         if win_x > 0 and x == o:
             return False
         
         if win_o > 0 and x > o:
             return False
 
         return True
                     


class Solution:
     def validTicTacToe(self, board):
         """
         :type board: List[str]
         :rtype: bool
         """
         valid_X,valid_O = 0,0
         cnt_X, cnt_O = 0,0
         # for i in range (3):
         #     if board[i] == 'OOO' or board[i] =='XXX':
         #         valid_row += 1
         #     cnt_X += board[i].count('X')
         #     cnt_O += board[i].count('O')
         # sum_row = sum(valid_row)
         for row in board:
             if row == 'XXX':
                 valid_X += 1
             elif row == 'OOO':
                 valid_O += 1
             cnt_X += row.count('X')
             cnt_O += row.count('O')
             
         a,b,c = board
         for col in zip(a,b,c):
             if col == 'XXX':
                 valid_X += 1
             elif col == 'OOO':
                 valid_O += 1
         if board[1][1] != ' ':   
             if board[0][0] == board[2][2] == board[1][1]:
                 if board[1][1] == 'X':
                     valid_X += 1
                 else:
                     valid_O += 1
             
             if board[2][0] == board[0][2] == board[1][1]:
                 if board[1][1] == 'X':
                     valid_X += 1
                 else:
                     valid_O += 1
             
         if valid_X + valid_O > 1:
             return False
         if valid_X:
             if cnt_X - cnt_O != 1:
                 return False
         elif valid_O:
             if cnt_X != cnt_O:
                 return False
         else:
             if not (0 <= cnt_X - cnt_O <= 1):
                 return False
         return True

class Solution:
     def validTicTacToe(self, board):
         """
         :type board: List[str]
         :rtype: bool
         """
         def Xwin(board):
             for r in range(2):
                 if board[r] == 'XXX':
                     return 1
                 if board[r] == 'OOO':
                     return -1
                 if board[0][r] == 'X' and board[1][r] == 'X' and board[2][r] == 'X':
                     return 1
                 if board[0][r] == 'O' and board[1][r] == 'O' and board[2][r] == 'O':
                     return -1
             if board[0][0] == 'X' and board[1][1] == 'X' and board[2][2] == 'X':
                 return 1
             if board[2][0] == 'X' and board[1][1] == 'X' and board[0][2] == 'X':
                 return 1
             if board[0][0] == 'O' and board[1][1] == 'O' and board[2][2] == 'O':
                 return -1
             if board[2][0] == 'O' and board[1][1] == 'O' and board[0][2] == 'O':
                 return -1
             return 0
         O, X = 0, 0
         for r in board:
             for c in r:
                 if c == 'O':
                     O += 1
                 elif c == 'X':
                     X += 1
         if O - X > 0:
             return False
         if X - O > 1:
             return False
         winner = Xwin(board)
         if winner == 1:
             return True if X - O == 1 else False
         elif winner == -1:
             return True if X - O == 0 else False
         return True

class Solution:
     def playerWon(self, board, player):
         for i in range(3):
             if board[0][i] == board[1][i] == board[2][i] == player:
                 return True
         for i in range(3):
             if board[i][0] == board[i][1] == board[i][2] == player:
                 return True
         if board[0][0] == board[1][1] == board [2][2] == player or\
         board[0][2] == board[1][1] == board[2][0] == player:
             return True
         return False
 
     def validTicTacToe(self, board):
         """
         :type board: List[str]
         :rtype: bool
         """
         count_x = sum(b.count("X") for b in board)
         count_o = sum(b.count("O") for b in board)
         if count_x - count_o > 1 or count_x - count_o < 0:
             return False
         if self.playerWon(board, "X") and count_x - count_o != 1:
             return False
         if self.playerWon(board, "O") and count_x - count_o != 0:
             return False
         return True

class Solution:
     def validTicTacToe(self, board):
         """
         :type board: List[str]
         :rtype: bool
         """
         o_cnt = 0
         x_cnt = 0
 
         bingo_x = 0
         bingo_o = 0
                 
         for i in range(3):
             if board[i] == 'O'*3:
                 bingo_o += 1
             if board[i] == 'X'*3:
                 bingo_x += 1
                 
             if board[0][i] == board[1][i] == board[2][i]:
                 if board[0][i] == 'O':
                     bingo_o += 1
                 if board[0][i] == 'X':
                     bingo_x += 1
             
             for j in range(3):
                 if board[i][j] == 'O':
                     o_cnt += 1
                 elif board[i][j] == 'X':
                     x_cnt += 1
         
         if x_cnt < o_cnt:
             return False
         elif x_cnt - o_cnt > 1:
             return False
         
         if  board[1][1] == board[0][2] == board[2][0]:
             if board[1][1] == 'O':
                 bingo_o += 1
             elif board[1][1] == 'X':
                 bingo_x += 1
 
         if board[0][0] == board[1][1] == board[2][2]:
             if board[0][0] == 'O':
                 bingo_o += 1
             elif board[0][0] == 'X':
                 bingo_x += 1
     
         if bingo_x >= 1 and bingo_o >= 1:
             return False
 
         if bingo_x >= 1 :
             return x_cnt == (o_cnt + 1)
         elif bingo_o >= 1:
             return x_cnt == o_cnt
             
         return True