Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1908.html

1908. Game of Nim

Level

Medium

Description

Alice and Bob take turns playing a game with Alice starting first.

In this game, there are n piles of stones. On each player’s turn, the player should remove any positive number of stones from a non-empty pile of his or her choice. The first player who cannot make a move loses, and the other player wins.

Given an integer array piles, where piles[i] is the number of stones in the i-th pile, return true if Alice wins, or false if Bob wins.

Both Alice and Bob play optimally.

Example 1:

Input: piles = [1]

Output: true

*Explanation:8 There is only one possible scenario:

• On the first turn, Alice removes one stone from the first pile. piles = [0].
• On the second turn, there are no stones left for Bob to remove. Alice wins.

Example 2:

Input: piles = [1,1]

Output: false

Explanation: It can be proven that Bob will always win. One possible scenario is:

• On the first turn, Alice removes one stone from the first pile. piles = [0,1].
• On the second turn, Bob removes one stone from the second pile. piles = [0,0].
• On the third turn, there are no stones left for Alice to remove. Bob wins.

Example 3:

Input: piles = [1,2,3]

Output: false

Explanation: It can be proven that Bob will always win. One possible scenario is:

• On the first turn, Alice removes three stones from the third pile. piles = [1,2,0].
• On the second turn, Bob removes one stone from the second pile. piles = [1,1,0].
• On the third turn, Alice removes one stone from the first pile. piles = [0,1,0].
• On the fourth turn, Bob removes one stone from the second pile. piles = [0,0,0].
• On the fifth turn, there are no stones left for Alice to remove. Bob wins.

Constraints:

• n == piles.length
• 1 <= n <= 7
• 1 <= piles[i] <= 7

Follow-up: Could you find a linear time solution?

Solution

For the game of Nim, where Alice starts first, Alice can win if and only if the bitwise xor results of all the elements in piles is not 0.

• Java
• C++
• Python
• Go
• TypeScript

• class Solution {
      public boolean nimGame(int[] piles) {
          int xor = 0;
          for (int pile : piles)
              xor ^= pile;
          return xor != 0;
      }
  }
  

• class Solution {
  public:
      bool nimGame(vector<int>& piles) {
          unordered_map<int, int> memo;
          int p[8] = {1};
          for (int i = 1; i < 8; ++i) {
              p[i] = p[i - 1] * 8;
          }
          auto f = [&](vector<int>& piles) {
              int st = 0;
              for (int i = 0; i < piles.size(); ++i) {
                  st += piles[i] * p[i];
              }
              return st;
          };
          function<bool(vector<int>&)> dfs = [&](vector<int>& piles) {
              int st = f(piles);
              if (memo.count(st)) {
                  return memo[st];
              }
              for (int i = 0; i < piles.size(); ++i) {
                  for (int j = 1; j <= piles[i]; ++j) {
                      piles[i] -= j;
                      if (!dfs(piles)) {
                          piles[i] += j;
                          return memo[st] = true;
                      }
                      piles[i] += j;
                  }
              }
              return memo[st] = false;
          };
          return dfs(piles);
      }
  };
  

• class Solution:
      def nimGame(self, piles: List[int]) -> bool:
          @cache
          def dfs(st):
              lst = list(st)
              for i, x in enumerate(lst):
                  for j in range(1, x + 1):
                      lst[i] -= j
                      if not dfs(tuple(lst)):
                          return True
                      lst[i] += j
              return False
  
          return dfs(tuple(piles))
  
  

• func nimGame(piles []int) bool {
  	memo := map[int]bool{}
  	p := make([]int, 8)
  	p[0] = 1
  	for i := 1; i < 8; i++ {
  		p[i] = p[i-1] * 8
  	}
  	f := func(piles []int) int {
  		st := 0
  		for i, x := range piles {
  			st += x * p[i]
  		}
  		return st
  	}
  	var dfs func(piles []int) bool
  	dfs = func(piles []int) bool {
  		st := f(piles)
  		if v, ok := memo[st]; ok {
  			return v
  		}
  		for i, x := range piles {
  			for j := 1; j <= x; j++ {
  				piles[i] -= j
  				if !dfs(piles) {
  					piles[i] += j
  					memo[st] = true
  					return true
  				}
  				piles[i] += j
  			}
  		}
  		memo[st] = false
  		return false
  	}
  	return dfs(piles)
  }
  

• function nimGame(piles: number[]): boolean {
      const p: number[] = Array(8).fill(1);
      for (let i = 1; i < 8; ++i) {
          p[i] = p[i - 1] * 8;
      }
      const f = (piles: number[]): number => {
          let st = 0;
          for (let i = 0; i < piles.length; ++i) {
              st += piles[i] * p[i];
          }
          return st;
      };
      const memo: Map<number, boolean> = new Map();
      const dfs = (piles: number[]): boolean => {
          const st = f(piles);
          if (memo.has(st)) {
              return memo.get(st)!;
          }
          for (let i = 0; i < piles.length; ++i) {
              for (let j = 1; j <= piles[i]; ++j) {
                  piles[i] -= j;
                  if (!dfs(piles)) {
                      piles[i] += j;
                      memo.set(st, true);
                      return true;
                  }
                  piles[i] += j;
              }
          }
          memo.set(st, false);
          return false;
      };
      return dfs(piles);
  }
  
  

All Problems

All Solutions