Juego de reemplazar elementos de array

Hay dos jugadores A y B que están interesados ​​en jugar un juego de números. En cada movimiento, un jugador elige dos números distintos, digamos a1 y a2 y luego reemplaza todos los a2 por a1 o a1 por a2 . Dejan de jugar si alguno de ellos no puede elegir dos números y el jugador que no puede elegir dos números distintos en una array, pierde el juego. El primer jugador siempre mueve primero y luego segundo. La tarea es encontrar qué jugador gana. 

Ejemplos: 

Input :  arr[] = { 1, 3, 3, 2,, 2, 1 }
Output : Player 2 wins
Explanation:
First plays always loses irrespective
of the numbers chosen by him. For example,
say first player picks ( 1 & 3) 
replace all 3 by 1  
Now array Become { 1, 1, 1, 2, 2, 1 }
Then second player picks ( 1  2 )
either he replace 1 by 2 or 2 by 1 
Array Become { 1, 1, 1, 1, 1, 1 }
Now first player is not able to choose.

Input  : arr[] = { 1, 2, 1, 2 }
Output : Player 1 wins

De los ejemplos anteriores, podemos observar que si el número de conteos de elementos distintos es par, el primer jugador siempre gana. De lo contrario, gana el segundo jugador.

Tomemos otro ejemplo: 

  int arr[] =  1, 2, 3, 4, 5, 6 

Aquí el número de elementos distintos es par (n). Si el jugador 1 elige dos números, digamos (4, 1), entonces nos quedamos con n-1 elemento distinto. Así que el segundo jugador se fue con n-1 elemento distinto. Este proceso continúa hasta que el elemento distinto se convierte en 1. Aquí n = 6  

Player   :  P1    p2    P1   p2    P1     P2    
distinct : [n, n-1, n-2, n-3, n-4, n-5 ]  
 
"At this point no distinct element left, 
so p2 is unable to pick two Dis element."

Debajo de la implementación de la idea anterior: 

// CPP program for Game of Replacement
#include <bits/stdc++.h>
using namespace std;
 
// Function return which player win the game
int playGame(int arr[], int n)
{
    // Create hash that will stores
    // all distinct element
    unordered_set<int> hash;
 
    // Traverse an array element
    for (int i = 0; i < n; i++)
        hash.insert(arr[i]);
 
    return (hash.size() % 2 == 0 ? 1 : 2);
}
 
// Driver Function
int main()
{
    int arr[] = { 1, 1, 2, 2, 2, 2 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    cout << "Player " << playGame(arr, n) << " Wins" << endl;
    return 0;
}

// Java program for Game of Replacement
import java.util.HashSet;
public class GameOfReplacingArrayElements
{
    // Function return which player win the game
    public static int playGame(int arr[])
    {
        // Create hash that will stores
        // all distinct element
        HashSet<Integer> set=new HashSet<>();
 
        // Traverse an array element
        for(int i:arr)
            set.add(i);
        return (set.size()%2==0)?1:2;
    }
 
    public static void main(String args[]) {
        int arr[] = { 1, 1, 2, 2, 2, 2 };
        System.out.print("Player "+playGame(arr)+" wins");
    }
}
//This code is contributed by Gaurav Tiwari

# Python program for Game of Replacement
 
# Function return which player win the game
def playGame(arr, n):
 
    # Create hash that will stores
    # all distinct element
    s = set()
 
    # Traverse an array element
    for i in range(n):
        s.add(arr[i])
    return 1 if len(s) % 2 == 0 else 2
 
# Driver code
arr = [1, 1, 2, 2, 2, 2]
n = len(arr)
print("Player",playGame(arr, n),"Wins")
 
# This code is contributed by Shrikant13

// C# program for Game of Replacement
using System;
using System.Collections.Generic;
 
public class GameOfReplacingArrayElements
{
    // Function return which player win the game
    public static int playGame(int []arr)
    {
        // Create hash that will stores
        // all distinct element
        HashSet<int> set = new HashSet<int>();
 
        // Traverse an array element
        foreach(int i in arr)
            set.Add(i);
        return (set.Count % 2 == 0) ? 1 : 2;
    }
 
    // Driver code
    public static void Main(String []args)
    {
        int []arr = { 1, 1, 2, 2, 2, 2 };
        Console.Write("Player " + playGame(arr) + " wins");
    }
}
 
// This code has been contributed by 29AjayKumar

<script>
 
// Javascript program for Game of Replacement
 
// Function return which player win the game
function playGame(arr, n)
{
 
    // Create hash that will stores
    // all distinct element
    var hash = new Set();
 
    // Traverse an array element
    for (var i = 0; i < n; i++)
        hash.add(arr[i]);
 
    return (hash.size % 2 == 0 ? 1 : 2);
}
 
// Driver Function
var arr = [1, 1, 2, 2, 2, 2];
var n = arr.length;
document.write( "Player " + playGame(arr, n) + " Wins" );
 
// This code is contributed by importantly.
</script>

Player 1 Wins

Complejidad de tiempo : O(n)