Optimal Game Strategy with Trays of Candies - ThoughtSpot Online Assessment IIT Guwahati

Problem Preview

"**Mode**: On-Campus **Exam Pattern**: 3 DSA qs in 90 mins **OA Date**: 2026-10-25 Two players, Player 1 and Player 2, play a game using N trays, where the i-th tray contains A[i] candies. The rules of the game are as follows: 1. Player 1 always makes the first move. 2. On each turn, a player must choose a tray containing candies and remove any positive, even number of candies from it. 3. If a tray becomes empty after a move, it is removed from the game. 4. Both players play optimally. 5. A player who cannot make a valid move loses the game. 6. Before the game begins, Player 2 can rearrange the trays in any order. Determine the number of distinct arrangements of the trays for which Player 1 wins, assuming both players play optimally. For this version, assume that **arrangements are considered distinct by position, even when some trays contain the same number of candies**, and that every tray contains a positive integer number of candies. ## Input Format - The first line contains an integer N, representing the number of trays. - The second line contains N space-separated integers A[1], A[2], ..., A[N], representing the number of candies in each tray. ## Output Format Print a single integer representing the number of arrangements that allow Player 1 to win. ## Example 1 **Input** ```text 3 1 2 3 ``` **Output** ```text 6 ``` **Explanation** There are 3 trays, containing 1, 2, and 3 candies. Under the assumed rules, the order of the trays does not affect the possible moves or the outcome of the game. Therefore, either all six positional arrangements allow Player 1 to win, or none do. For this illustrative example, assume Player 1 wins for this set of tray sizes. Since all three tray sizes are distinct, there are 3! = 6 distinct arrangements, so the answer is 6. ## Constraints - 1 ≤ N ≤ 10^5 - 1 ≤ A[i] ≤ 10^9"