Two players, player1 and player2, are playing a game on a given number sequence S where player1 starts first and both of them play optimally. The task is to find whether player1 wins or loses. If he wins, print “Yes”, otherwise print “No”.
The rules of the game are as follows:
- The player’s alternate turns.
- In each turn, the current player must choose one or more elements of the current sequence S such that the values of all chosen elements are identical, and erase these elements from S.
- When a player cannot choose anything (the sequence S is already empty), this player loses the game.
Examples:
Input: S = {2, 1, 2, 2}
Output: Yes
Explanation:
The first player can choose the subset of elements with indices {0, 3} {0, 2} or {2, 3} (in the sequence) to ensure his victory in the future.Input: S = {3, 2, 2, 3, 3, 5}
Output:No
Explanation:
The first player can not win in this sequence.
If player1 chooses 2 and removes all the 2 from the sequence, then player2 will choose two 3 and remove only two 3 as both players play optimally.
Then player1 removes either 3 or 5 and player2 will remove the final element. So player1 will always lose.
Approach: The approach to the above problem can be given as if the total number of elements in sequence is even and the number of elements that occur more than once is also even, then the first player can not win. If the number of elements that occur more than once is odd and the occurrence of repeated elements is greater than or equal to 4 and a multiple of 2, then the first player can not win. Otherwise, player1 can be the winner.
Below is the implementation of the above approach:
C++
// C++ implementation for Two player// game in which a player can remove// all occurrences of a number#include <bits/stdc++.h>using namespace std;// Function that print whether// player1 can wins or losesvoid game(int v[], int n){ unordered_map<int, int> m; // storing the number of occurrence // of elements in unordered map for (int i = 0; i < n; i++) { if (m.find(v[i]) == m.end()) m[v[i]] = 1; else m[v[i]]++; } int count = 0; // variable to check if the // occurrence of repeated // elements is >= 4 and // multiple of 2 or not int check = 0; // count elements which // occur more than once for (auto i : m) { if (i.second > 1) { if (i.second >= 4 && i.second % 2 == 0) check++; count++; } } if (check % 2 != 0) cout << "Yes" << endl; else if (n % 2 == 0 && count % 2 == 0) cout << "No" << endl; else cout << "Yes" << endl;}// Driver codeint main(){ int arr[] = { 3, 2, 2, 3, 3, 5 }; int size = sizeof(arr) / sizeof(arr[0]); game(arr, size); return 0;} |
Java
// Java implementation for Two player// game in which a player can remove// all occurrences of a numberimport java.util.*;class GFG { // Function that print whether // player1 can wins or loses public static void game(int[] v, int n) { HashMap<Integer, Integer> m = new HashMap<>(); // Storing the number of occurrence // of elements in unordered map for (int i = 0; i < n; i++) { if (!m.containsKey(v[i])) m.put(v[i], 1); else m.replace(v[i], m.get(v[i]) + 1); } int count = 0; // variable to check if the // occurrence of repeated // elements is >= 4 and // multiple of 2 or not int check = 0; // count elements which // occur more than once for (Map.Entry<Integer, Integer> i : m.entrySet()) { if (i.getValue() > 1) { if (i.getValue() >= 4 && i.getValue() % 2 == 0) check++; count++; } } if (check % 2 != 0) flag = false; if (check % 2 != 0) System.out.println("Yes"); else if (n % 2 == 0 && count % 2 == 0) System.out.println("No"); else System.out.println("Yes"); } public static void main(String[] args) { int[] arr = { 3, 2, 2, 3, 3, 5 }; int size = arr.length; game(arr, size); }}// This code is contributed by divyeshrabadiya07 |
Python3
# Python3 implementation for two player# game in which a player can remove# all occurrences of a numberfrom collections import defaultdict# Function that print whether# player1 can wins or losesdef game(v, n): m = defaultdict(int) # Storing the number of occurrence # of elements in unordered map for i in range(n): if (v[i] not in m): m[v[i]] = 1 else: m[v[i]] += 1 count = 0 # Variable to check if the # occurrence of repeated # elements is >= 4 and # multiple of 2 or not check = 0 # Count elements which # occur more than once for i in m.values(): if (i > 1): if (i >= 4 and i % 2 == 0): check += 1 count += 1 if (check % 2 != 0): print("Yes") elif (n % 2 == 0 and count % 2 == 0): print("No") else: print("Yes")# Driver codeif __name__ == "__main__": arr = [3, 2, 2, 3, 3, 5] size = len(arr) game(arr, size)# This code is contributed by chitranayal |
C#
// C# implementation for Two player// game in which a player can remove// all occurrences of a numberusing System;using System.Collections.Generic;class GFG { // Function that print whether // player1 can wins or loses public static void game(int[] v, int n) { Dictionary<int, int> m = new Dictionary<int, int>(); // Storing the number of occurrence // of elements in unordered map for (int i = 0; i < n; i++) { if (!m.ContainsKey(v[i])) m.Add(v[i], 1); else m[v[i]] = m[v[i]] + 1; } int count = 0; // Variable to check if the // occurrence of repeated // elements is >= 4 and // multiple of 2 or not int check = 0; // Count elements which // occur more than once foreach(KeyValuePair<int, int> i in m) { if (i.Value > 1) { if (i.Value >= 4 && i.Value % 2 == 0) check++; count++; } } if (check % 2 != 0) flag = false; if (check % 2 != 0) Console.WriteLine("Yes"); else if (n % 2 == 0 && count % 2 == 0) Console.WriteLine("No"); else Console.WriteLine("Yes"); } // Driver code public static void Main(String[] args) { int[] arr = { 3, 2, 2, 3, 3, 5 }; int size = arr.Length; game(arr, size); }}// This code is contributed by Amit Katiyar |
Javascript
<script>// Java implementation for Two player// game in which a player can remove// all occurrences of a number// Function that print whether// player1 can wins or losesfunction game(v,n){ let m = new Map(); // Storing the number of occurrence // of elements in unordered map for (let i = 0; i < n; i++) { if (!m.has(v[i])) m.set(v[i], 1); else m.set(v[i], m.get(v[i]) + 1); } let count = 0; // variable to check if the // occurrence of repeated // elements is >= 4 and // multiple of 2 or not let check = 0; // count elements which // occur more than once for (let [key, value] of m.entries()) { if(value> 1) { if(value >= 4 && value % 2 == 0) check++; count++; } } let flag; if (check % 2 != 0) document.write("Yes<br>"); else if (n % 2 == 0 && count % 2 == 0) document.write("No<br>"); else document.write("Yes<br>");}let arr=[3, 2, 2, 3, 3, 5];let size = arr.length;game(arr, size);// This code is contributed by avanitrachhadiya2155</script> |
No
Time complexity: The complexity of the above approach is O(N).
Auxiliary Space: O(N), for storing elements in the HashMap.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
