Dos jugadores A y B están jugando NIM Game entre sí. Ambos están jugando de manera óptima. El jugador A comienza el juego. La tarea es encontrar el número de formas de jugar el 1er movimiento para A para asegurar una estrategia ganadora para A si es posible, de lo contrario imprima -1 .
Ejemplos:
Entrada: arr[] = {1, 2, 3}
Salida: -1
No hay una estrategia ganadora para A sin importar qué tan bien juegue.
Entrada: arr[] = {2, 4, 5}
Salida: 1
Para jugar de manera óptima, A elegirá una moneda del primer montón y ese es el único movimiento óptimo.
Acercarse:
- Primero verifique quién ganará el juego tomando XOR de todos los elementos de la array si XOR es cero, entonces no importa cuán óptimamente juegue A, A siempre perderá. Si XOR no es cero, vaya al Paso 2.
- Verificaremos para cada pila si podemos quitar algunas monedas de esa pila para que después de este movimiento, el XOR de todos los elementos de la array sea cero. Entonces, para todas las pilas, uno por uno tomaremos xor de todos los elementos restantes de la array y verificaremos si el valor de XOR es mayor que la cantidad de monedas en la pila. Si es así, no es posible jugar el primer movimiento usando esta pila porque solo podemos quitar monedas de la pila en un movimiento y no podemos agregar monedas. De lo contrario, incrementaremos el número de formas.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Utility function to return the XOR
// of all the array elements
int xorArray(int arr[], int n)
{
int res = 0;
for (int i = 0; i < n; i++)
res = res ^ arr[i];
return res;
}
// Function to return the count of ways
// to play the first move optimally
int getTotalWays(int arr[], int n)
{
// XOR of all the array elements
int xorArr = xorArray(arr, n);
// The player making the first move
// can't win the game no matter
// how optimally he plays
if (xorArr == 0)
return -1;
// Initialised with zero
int numberOfWays = 0;
for (int i = 0; i < n; i++) {
// requiredCoins is the number of coins
// the player making the move must leave
// in the current pile in order to play optimally
int requiredCoins = xorArr ^ arr[i];
// If requiredCoins is less than the current
// amount of coins in the current pile
// then only the player can make an optimal move
if (requiredCoins < arr[i])
numberOfWays++;
}
return numberOfWays;
}
// Driver code
int main()
{
// Coins in each pile
int arr[] = { 3, 4, 4, 2 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << getTotalWays(arr, n);
return 0;
}
Java
// Java implementation of the approach
class GFG
{
// Utility function to return the XOR
// of all the array elements
static int xorArray(int arr[], int n)
{
int res = 0;
for (int i = 0; i < n; i++)
res = res ^ arr[i];
return res;
}
// Function to return the count of ways
// to play the first move optimally
static int getTotalWays(int arr[], int n)
{
// XOR of all the array elements
int xorArr = xorArray(arr, n);
// The player making the first move
// can't win the game no matter
// how optimally he plays
if (xorArr == 0)
return -1;
// Initialised with zero
int numberOfWays = 0;
for (int i = 0; i < n; i++)
{
// requiredCoins is the number of coins
// the player making the move must leave
// in the current pile in order to play optimally
int requiredCoins = xorArr ^ arr[i];
// If requiredCoins is less than the current
// amount of coins in the current pile
// then only the player can make an optimal move
if (requiredCoins < arr[i])
numberOfWays++;
}
return numberOfWays;
}
// Driver code
public static void main(String[] args)
{
// Coins in each pile
int arr[] = { 3, 4, 4, 2 };
int n =arr.length;
System.out.println(getTotalWays(arr, n));
}
}
// This code is contributed by Code_Mech
Python3
# Python3 implementation of the approach # Utility function to return the # XOR of all the array elements def xorArray(arr, n): res = 0 for i in range(0, n): res = res ^ arr[i] return res # Function to return the count of ways # to play the first move optimally def getTotalWays(arr, n): # XOR of all the array elements xorArr = xorArray(arr, n) # The player making the first move # can't win the game no matter # how optimally he plays if xorArr == 0: return -1 # Initialised with zero numberOfWays = 0 for i in range(0, n): # requiredCoins is the number of coins the # player making the move must leave in the # current pile in order to play optimally requiredCoins = xorArr ^ arr[i] # If requiredCoins is less than the current # amount of coins in the current pile # then only the player can make an optimal move if requiredCoins < arr[i]: numberOfWays += 1 return numberOfWays # Driver code if __name__ == "__main__": # Coins in each pile arr = [3, 4, 4, 2] n = len(arr) print(getTotalWays(arr, n)) # This code is contributed by Rituraj Jain
C#
// C# implementation of the approach
using System;
class GFG
{
// Utility function to return the XOR
// of all the array elements
static int xorArray(int []arr, int n)
{
int res = 0;
for (int i = 0; i < n; i++)
res = res ^ arr[i];
return res;
}
// Function to return the count of ways
// to play the first move optimally
static int getTotalWays(int []arr, int n)
{
// XOR of all the array elements
int xorArr = xorArray(arr, n);
// The player making the first move
// can't win the game no matter
// how optimally he plays
if (xorArr == 0)
return -1;
// Initialised with zero
int numberOfWays = 0;
for (int i = 0; i < n; i++)
{
// requiredCoins is the number of coins
// the player making the move must leave
// in the current pile in order to play optimally
int requiredCoins = xorArr ^ arr[i];
// If requiredCoins is less than the current
// amount of coins in the current pile
// then only the player can make an optimal move
if (requiredCoins < arr[i])
numberOfWays++;
}
return numberOfWays;
}
// Driver code
static public void Main ()
{
// Coins in each pile
int []arr = { 3, 4, 4, 2 };
int n = arr.Length;
Console.Write(getTotalWays(arr, n));
}
}
// This code is contributed by ajit.
PHP
<?php
// PHP implementation of the approach
// Utility function to return the XOR
// of all the array elements
function xorArray($arr, $n)
{
$res = 0;
for ($i = 0; $i < $n; $i++)
$res = $res ^ $arr[$i];
return $res;
}
// Function to return the count of ways
// to play the first move optimally
function getTotalWays($arr, $n)
{
// XOR of all the array elements
$xorArr = xorArray($arr, $n);
// The player making the first move
// can't win the game no matter
// how optimally he plays
if ($xorArr == 0)
return -1;
// Initialised with zero
$numberOfWays = 0;
for ($i = 0; $i < $n; $i++)
{
// requiredCoins is the number of coins
// the player making the move must leave
// in the current pile in order to play optimally
$requiredCoins = $xorArr ^ $arr[$i];
// If requiredCoins is less than the current
// amount of coins in the current pile
// then only the player can make an optimal move
if ($requiredCoins < $arr[$i])
$numberOfWays++;
}
return $numberOfWays;
}
// Driver code
// Coins in each pile
$arr = array(3, 4, 4, 2 );
$n = sizeof($arr);
echo getTotalWays($arr, $n);
// This code is contributed
// by Akanksha Rai
?>
Javascript
<script>
// Javascript implementation of the approach
// Utility function to return the XOR
// of all the array elements
function xorArray(arr, n)
{
let res = 0;
for (let i = 0; i < n; i++)
res = res ^ arr[i];
return res;
}
// Function to return the count of ways
// to play the first move optimally
function getTotalWays(arr, n)
{
// XOR of all the array elements
let xorArr = xorArray(arr, n);
// The player making the first move
// can't win the game no matter
// how optimally he plays
if (xorArr == 0)
return -1;
// Initialised with zero
let numberOfWays = 0;
for (let i = 0; i < n; i++) {
// requiredCoins is the number of coins
// the player making the move must leave
// in the current pile in order to play optimally
let requiredCoins = xorArr ^ arr[i];
// If requiredCoins is less than the current
// amount of coins in the current pile
// then only the player can make an optimal move
if (requiredCoins < arr[i])
numberOfWays++;
}
return numberOfWays;
}
// Driver code
// Coins in each pile
let arr = [ 3, 4, 4, 2 ];
let n = arr.length;
document.write(getTotalWays(arr, n));
// This code is contributed by souravmahato348.
</script>
Producción:
1
Complejidad de tiempo: O(N)
Publicación traducida automáticamente
Artículo escrito por saurabh_mittal y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA