Juego de dos jugadores en el que un jugador puede eliminar todas las apariciones de un número

Dos jugadores, el jugador 1 y el jugador 2, están jugando un juego en una secuencia numérica dada S donde el jugador 1 comienza primero y ambos juegan de manera óptima. La tarea es encontrar si el jugador 1 gana o pierde. Si gana, escriba «Sí», de lo contrario, escriba «No». 
Las reglas del juego son las siguientes: 

• Los turnos alternos del jugador.
• En cada turno, el jugador actual debe elegir uno o más elementos de la secuencia actual S de modo que los valores de todos los elementos elegidos sean idénticos y borrar estos elementos de S.
• Cuando un jugador no puede elegir nada (la secuencia S ya está vacía), este jugador pierde el juego.

Ejemplos: 

Entrada: S = {2, 1, 2, 2} 
Salida: Sí 
Explicación: 
El primer jugador puede elegir el subconjunto de elementos con índices {0, 3} {0, 2} o {2, 3} (en la secuencia) para asegurar su victoria en el futuro.

Entrada: S = {3, 2, 2, 3, 3, 5} 
Salida: No 
Explicación: 
El primer jugador no puede ganar en esta secuencia. 
Si el jugador 1 elige 2 y elimina todos los 2 de la secuencia, el jugador 2 elegirá dos 3 y eliminará solo dos 3, ya que ambos jugadores juegan de manera óptima. 
Luego , el jugador 1 elimina 3 o 5 y el jugador 2 eliminará el elemento final. Entonces el jugador 1 siempre perderá. 

Enfoque: El enfoque del problema anterior se puede dar como si el número total de elementos en secuencia fuera par y el número de elementos que ocurren más de una vez también fuera par, entonces el primer jugador no puede ganar. Si el número de elementos que ocurren más de una vez es impar y la ocurrencia de elementos repetidos es mayor o igual a 4 y múltiplo de 2, entonces el primer jugador no puede ganar. De lo contrario, el jugador 1 puede ser el ganador.

A continuación se muestra la implementación del enfoque anterior: 

// 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 loses
void 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)
        bool flag = false;
 
    if (check % 2 != 0)
        cout << "Yes" << endl;
 
    else if (n % 2 == 0
&& count % 2 == 0)
        cout << "No" << endl;
 
    else
        cout << "Yes" << endl;
}
 
// Driver code
int main()
{
 
    int arr[] = { 3, 2, 2, 3, 3, 5 };
 
    int size = sizeof(arr)
/ sizeof(arr[0]);
 
    game(arr, size);
 
    return 0;
}

// Java implementation for Two player
// game in which a player can remove
// all occurrences of a number
import 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++;
    }
  }
   
  boolean flag;
   
  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 implementation for two player
# game in which a player can remove
# all occurrences of a number
from collections import defaultdict
 
# Function that print whether
# player1 can wins or loses
def 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):
        flag = False
 
    if (check % 2 != 0):
        print("Yes")
 
    elif (n % 2 == 0 and count % 2 == 0):
        print("No")
         
    else:
        print("Yes")
 
# Driver code
if __name__ == "__main__":
     
    arr = [ 3, 2, 2, 3, 3, 5 ]
    size = len(arr)
     
    game(arr, size)
 
# This code is contributed by chitranayal

// C# implementation for Two player
// game in which a player can remove
// all occurrences of a number
using 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++;
        }
    }
     
    bool flag;
     
    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

<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 loses
function 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)
    flag = false;
  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

Complejidad del tiempo: La complejidad del enfoque anterior es O(N).