Dada una array arr[] de enteros positivos distintos, dos jugadores A y B están jugando un juego. En cada movimiento, un jugador selecciona dos números xey de la array y si | x – y| no está presente en la array, entonces el jugador agrega este número a la array (el tamaño de la array aumenta en 1). El jugador que no puede hacer el movimiento pierde el juego. La tarea es encontrar al ganador del juego si el jugador A siempre comienza el juego.
Ejemplos:
Entrada: arr[] = {2, 3}
Salida: A
Después del movimiento de A, el arreglo será {2, 3, 1} y B no puede hacer ningún movimiento.
Entrada: arr[] = {5, 6, 7}
Salida: B
Enfoque: Observe aquí que al final del juego (cuando no hay más movimientos para hacer), la array resultante contendrá todos los múltiplos del gcd de la array original hasta el elemento máximo de la array original.
Por ejemplo, arr[] = {8, 10}
Dado que, mcd(8, 10) = 2. Entonces, la array resultante al final del juego contendrá todos los múltiplos de 2 ≤ max(arr), es decir, 10.
Por lo tanto, array[] = {2, 4, 6, 8, 10}
A partir de la observación anterior, se puede encontrar el número de movimientos que se pueden realizar en la array original, lo que determinará el ganador del juego, si el número de movimientos es par, B será el ganador del juego; de lo contrario, A gana el juego . .
El número de movimientos se puede encontrar como, (max(arr) / gcd) – n donde gcd es el mcd de los elementos del arreglo original y max(arr) / gcd da el número total de elementos en el arreglo resultante. Restar el recuento original de elementos del recuento de elementos en la array resultante dará el número de movimientos.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the winner of the game
char getWinner(int arr[], int n)
{
// To store the gcd of the original array
int gcd = arr[0];
// To store the maximum element
// from the original array
int maxEle = arr[0];
for (int i = 1; i < n; i++) {
gcd = __gcd(gcd, arr[i]);
maxEle = max(maxEle, arr[i]);
}
int totalMoves = (maxEle / gcd) - n;
// If number of moves are odd
if (totalMoves % 2 == 1)
return 'A';
return 'B';
}
// Driver Code
int main()
{
int arr[] = { 5, 6, 7 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << getWinner(arr, n);
return 0;
}
Java
// Java implementation of the approach
class GFG
{
// Function to calculate gcd
static int __gcd(int a, int b)
{
if (b == 0)
return a;
return __gcd(b, a % b);
}
// Function to return the winner
// of the game
static char getWinner(int []arr, int n)
{
// To store the gcd of the
// original array
int gcd = arr[0];
// To store the maximum element
// from the original array
int maxEle = arr[0];
for (int i = 1; i < n; i++)
{
gcd = __gcd(gcd, arr[i]);
maxEle = Math.max(maxEle, arr[i]);
}
int totalMoves = (maxEle / gcd) - n;
// If number of moves are odd
if (totalMoves % 2 == 1)
return 'A';
return 'B';
}
// Driver Code
public static void main(String args[])
{
int []arr = { 5, 6, 7 };
int n = arr.length;
System.out.print(getWinner(arr, n));
}
}
// This code is contributed
// by Akanksha Rai
Python3
# Python3 implementation of the approach from math import gcd # Function to return the winner # of the game def getWinner(arr, n) : # To store the gcd of the # original array __gcd = arr[0]; # To store the maximum element # from the original array maxEle = arr[0]; for i in range(1, n) : __gcd = gcd(__gcd, arr[i]); maxEle = max(maxEle, arr[i]); totalMoves = (maxEle / __gcd) - n; # If number of moves are odd if (totalMoves % 2 == 1) : return 'A'; return 'B'; # Driver Code if __name__ == "__main__" : arr = [ 5, 6, 7 ]; n = len(arr) print(getWinner(arr, n)) # This code is contributed by Ryuga
C#
// C# implementation of the approach
using System;
class GFG
{
// Function to calculate gcd
static int __gcd(int a, int b)
{
if (b == 0)
return a;
return __gcd(b, a % b);
}
// Function to return the winner
// of the game
static char getWinner(int []arr, int n)
{
// To store the gcd of the
// original array
int gcd = arr[0];
// To store the maximum element
// from the original array
int maxEle = arr[0];
for (int i = 1; i < n; i++)
{
gcd = __gcd(gcd, arr[i]);
maxEle = Math.Max(maxEle, arr[i]);
}
int totalMoves = (maxEle / gcd) - n;
// If number of moves are odd
if (totalMoves % 2 == 1)
return 'A';
return 'B';
}
// Driver Code
public static void Main()
{
int []arr = { 5, 6, 7 };
int n = arr.Length;
Console.Write(getWinner(arr, n));
}
}
// This code is contributed
// by Akanksha Rai
PHP
<?php
// PHP implementation of the approach
// Function to calculate gcd
function __gcd($a, $b)
{
if ($b == 0)
return $a;
return __gcd($b, $a % $b);
}
// Function to return the winner
// of the game
function getWinner($arr, $n)
{
// To store the gcd of the
// original array
$gcd = $arr[0];
// To store the maximum element
// from the original array
$maxEle = $arr[0];
for ($i = 1; $i < $n; $i++)
{
$gcd = __gcd($gcd, $arr[$i]);
$maxEle = max($maxEle, $arr[$i]);
}
$totalMoves = ($maxEle / $gcd) - $n;
// If number of moves are odd
if ($totalMoves % 2 == 1)
return 'A';
return 'B';
}
// Driver Code
$arr = array(5, 6, 7);
$n = sizeof($arr);
echo getWinner($arr, $n);
// This code is contributed
// by Akanksha Rai
?>
Javascript
<script>
// JavaScript implementation of the approach
// Function to calculate gcd
function __gcd(a, b)
{
if (b == 0)
return a;
return __gcd(b, a % b);
}
// Function to return the winner
// of the game
function getWinner(arr, n)
{
// To store the gcd of the
// original array
let gcd = arr[0];
// To store the maximum element
// from the original array
let maxEle = arr[0];
for (let i = 1; i < n; i++)
{
gcd = __gcd(gcd, arr[i]);
maxEle = Math.max(maxEle, arr[i]);
}
let totalMoves = parseInt(maxEle / gcd, 10) - n;
// If number of moves are odd
if (totalMoves % 2 == 1)
return 'A';
return 'B';
}
let arr = [ 5, 6, 7 ];
let n = arr.length;
document.write(getWinner(arr, n));
</script>
B
Complejidad de tiempo: O (nlogn)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por pawan_asipu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA