Dada una array arr[] de tamaño N , la tarea es encontrar el ganador del juego cuando dos jugadores juegan de manera óptima según las siguientes reglas:
- El jugador 1 comienza el juego.
- En cada turno, un jugador elimina un elemento de la array.
- El jugador 2 ganará el juego solo si el GCD de todos los elementos eliminados por el jugador 1 se vuelve igual a 1 .
Ejemplos:
Entrada: arr[] = { 2, 4, 8 }
Salida: Jugador 1
Explicación:
Turno 1: El jugador 1 elimina arr[0]. Por lo tanto, GCD de elementos eliminados por el Jugador 1 = 2
Turno 2: Dado que GCD de elementos eliminados por el Jugador 1 no es igual a 1. Por lo tanto, el Jugador 2 elimina arr[1].
Turno 3: El jugador 1 elimina arr[2]. Por lo tanto, MCD de los elementos eliminados por el jugador 1 = MCD(2, 8) = 2
Dado que el MCD de los elementos eliminados por el jugador 1 no es igual a 1, el jugador 1 gana el juego.Entrada: arr[] = { 2, 1, 1, 1, 1, 1 }
Salida : Jugador 2
Turno 1: Jugador 1 elimina arr[0]. Por lo tanto, GCD de los elementos eliminados por el Jugador 1 = 2
Turno 2: Dado que el GCD de los elementos eliminados por el Jugador 1 no es igual a 1, el Jugador 2 elimina arr[1].
Turno 3: El jugador 1 elimina arr[2]. Por lo tanto, MCD de los elementos eliminados por el jugador 1 = MCD(2, 1) = 1
Dado que el MCD de los elementos eliminados por el jugador 1 es 1, el jugador 2 gana el juego.
Enfoque: la forma óptima para el jugador 1 y el jugador 2 es eliminar siempre los elementos de la array que tienen al menos un factor primo común en la mayoría de los elementos de la array. Siga los pasos a continuación para resolver el problema:
- Inicialice un Map , digamos mp , de modo que mp[i] almacene el recuento de elementos de array cuyo factor primo es i
- Recorra el mapa y encuentre el valor máximo presente en el Mapa , digamos maxCnt .
- Si N es un número impar y maxCnt es igual a N o si N es un número par y maxCnt ≥ N – 1 , entonces el jugador 1 gana el juego.
- De lo contrario, el jugador 2 gana el juego.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the winner of the game by
// removing array elements whose GCD is 1
void findWinnerGameRemoveGCD(int arr[], int n)
{
// mp[i]: Stores count of array
// elements whose prime factor is i
unordered_map<int, int> mp;
// Traverse the array
for (int i = 0; i < n; i++) {
// Calculate the prime factors
// of arr[i]
for (int j = 2; j * j <= arr[i];
j++) {
// If arr[i] is divisible by j
if (arr[i] % j == 0) {
// Update mp[j]
mp[j]++;
while (arr[i] % j == 0) {
// Update arr[i]
arr[i] = arr[i] / j;
}
}
}
// If arr[i] exceeds 1
if (arr[i] > 1) {
mp[arr[i]]++;
}
}
// Stores maximum value
// present in the Map
int maxCnt = 0;
// Traverse the map
for (auto i : mp) {
// Update maxCnt
maxCnt = max(maxCnt,
i.second);
}
// If n is an even number
if (n % 2 == 0) {
// If maxCnt is greater
// than or equal to n-1
if (maxCnt >= n - 1) {
// Player 1 wins
cout << "Player 1";
}
else {
// Player 2 wins
cout << "Player 2";
}
}
else {
// If maxCnt equal to n
if (maxCnt == n) {
// Player 1 wins
cout << "Player 1";
}
else {
// Player 2 wins
cout << "Player 2";
}
}
}
// Driver Code
int main()
{
int arr[] = { 2, 4, 8 };
int N = sizeof(arr)
/ sizeof(arr[0]);
findWinnerGameRemoveGCD(arr, N);
return 0;
}
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG{
// Function to find the winner of the game by
// removing array elements whose GCD is 1
static void findWinnerGameRemoveGCD(int arr[], int n)
{
// mp[i]: Stores count of array
// elements whose prime factor is i
HashMap<Integer,
Integer> mp = new HashMap<Integer,
Integer>();
// Traverse the array
for (int i = 0; i < n; i++) {
// Calculate the prime factors
// of arr[i]
for (int j = 2; j * j <= arr[i];
j++) {
// If arr[i] is divisible by j
if (arr[i] % j == 0) {
// Update mp[j]
if (mp.containsKey(j))
{
mp.put(j, mp.get(j) + 1);
}
else
{
mp.put(j, 1);
}
while (arr[i] % j == 0) {
// Update arr[i]
arr[i] = arr[i] / j;
}
}
}
// If arr[i] exceeds 1
if (arr[i] > 1) {
if(mp.containsKey(arr[i]))
{
mp.put(arr[i], mp.get(arr[i]) + 1);
}
else
{
mp.put(arr[i], 1);
}
}
}
// Stores maximum value
// present in the Map
int maxCnt = 0;
// Traverse the map
for (Map.Entry<Integer,
Integer> i : mp.entrySet()) {
// Update maxCnt
maxCnt = Math.max(maxCnt, i.getValue());
}
// If n is an even number
if (n % 2 == 0) {
// If maxCnt is greater
// than or equal to n-1
if (maxCnt >= n - 1) {
// Player 1 wins
System.out.print("Player 1");
}
else {
// Player 2 wins
System.out.print("Player 2");
}
}
else {
// If maxCnt equal to n
if (maxCnt == n) {
// Player 1 wins
System.out.print("Player 1");
}
else {
// Player 2 wins
System.out.print("Player 2");
}
}
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 2, 4, 8 };
int N = arr.length;
findWinnerGameRemoveGCD(arr, N);
}
}
// This code is contributed by susmitakundugoaldanga
Python3
# Python3 program to implement
# the above approach
# Function to find the winner of the game by
# removing array elements whose GCD is 1
def findWinnerGameRemoveGCD(arr, n) :
# mp[i]: Stores count of array
# elements whose prime factor is i
mp = dict.fromkeys(arr, 0);
# Traverse the array
for i in range(n) :
# Calculate the prime factors
# of arr[i]
for j in range(2, int(arr[i] * (1/2)) + 1) :
# If arr[i] is divisible by j
if (arr[i] % j == 0) :
# Update mp[j]
mp[j] += 1;
while (arr[i] % j == 0) :
# Update arr[i]
arr[i] = arr[i] // j;
# If arr[i] exceeds 1
if (arr[i] > 1) :
mp[arr[i]] += 1;
# Stores maximum value
# present in the Map
maxCnt = 0;
# Traverse the map
for i in mp:
# Update maxCnt
maxCnt = max(maxCnt,mp[i]);
# If n is an even number
if (n % 2 == 0) :
# If maxCnt is greater
# than or equal to n-1
if (maxCnt >= n - 1) :
# Player 1 wins
print("Player 1",end="");
else :
# Player 2 wins
print("Player 2",end="");
else :
# If maxCnt equal to n
if (maxCnt == n) :
# Player 1 wins
print("Player 1",end="");
else :
# Player 2 wins
print("Player 2",end="");
# Driver Code
if __name__ == "__main__" :
arr = [ 2, 4, 8 ];
N = len(arr);
findWinnerGameRemoveGCD(arr, N);
# This code is contributed by AnkThon
C#
// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to find the winner of the game by
// removing array elements whose GCD is 1
static void findWinnerGameRemoveGCD(int []arr, int n)
{
// mp[i]: Stores count of array
// elements whose prime factor is i
Dictionary<int,
int> mp = new Dictionary<int,
int>();
// Traverse the array
for (int i = 0; i < n; i++) {
// Calculate the prime factors
// of arr[i]
for (int j = 2; j * j <= arr[i];
j++) {
// If arr[i] is divisible by j
if (arr[i] % j == 0)
{
// Update mp[j]
if (mp.ContainsKey(j))
{
mp[j] = mp[j] + 1;
}
else
{
mp.Add(j, 1);
}
while (arr[i] % j == 0)
{
// Update arr[i]
arr[i] = arr[i] / j;
}
}
}
// If arr[i] exceeds 1
if (arr[i] > 1)
{
if(mp.ContainsKey(arr[i]))
{
mp[arr[i]] = mp[arr[i]] + 1;
}
else
{
mp.Add(arr[i], 1);
}
}
}
// Stores maximum value
// present in the Map
int maxCnt = 0;
// Traverse the map
foreach (KeyValuePair<int,
int> i in mp)
{
// Update maxCnt
maxCnt = Math.Max(maxCnt, i.Value);
}
// If n is an even number
if (n % 2 == 0)
{
// If maxCnt is greater
// than or equal to n-1
if (maxCnt >= n - 1)
{
// Player 1 wins
Console.Write("Player 1");
}
else
{
// Player 2 wins
Console.Write("Player 2");
}
}
else
{
// If maxCnt equal to n
if (maxCnt == n)
{
// Player 1 wins
Console.Write("Player 1");
}
else
{
// Player 2 wins
Console.Write("Player 2");
}
}
}
// Driver code
public static void Main(String[] args)
{
int []arr = { 2, 4, 8 };
int N = arr.Length;
findWinnerGameRemoveGCD(arr, N);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// JavaScript program to implement
// the above approach
// Function to find the winner of the game by
// removing array elements whose GCD is 1
function findWinnerGameRemoveGCD(arr, n)
{
// mp[i]: Stores count of array
// elements whose prime factor is i
let mp = new Map();
// Traverse the array
for (let i = 0; i < n; i++) {
// Calculate the prime factors
// of arr[i]
for (let j = 2; j * j <= arr[i];j++) {
// If arr[i] is divisible by j
if (arr[i] % j == 0) {
// Update mp[j]
if(mp.has(j)){
mp.set(j,mp.get(j)+1);
}
else mp.set(j,1);
while (arr[i] % j == 0) {
// Update arr[i]
arr[i] = Math.floor(arr[i] / j);
}
}
}
// If arr[i] exceeds 1
if (arr[i] > 1) {
if(mp.has(arr[i])){
mp.set(arr[i],mp.get(arr[i])+1);
}
else mp.set(arr[i],1);
}
}
// Stores maximum value
// present in the Map
let maxCnt = 0;
// Traverse the map
for (let [i,j] of mp) {
// Update maxCnt
maxCnt = Math.max(maxCnt,j);
}
// If n is an even number
if (n % 2 == 0) {
// If maxCnt is greater
// than or equal to n-1
if (maxCnt >= n - 1) {
// Player 1 wins
document.write("Player 1");
}
else {
// Player 2 wins
document.write("Player 2");
}
}
else {
// If maxCnt equal to n
if (maxCnt == n) {
// Player 1 wins
document.write("Player 1");
}
else {
// Player 2 wins
document.write("Player 2");
}
}
}
// Driver Code
let arr = [ 2, 4, 8 ];
let N = arr.length;
findWinnerGameRemoveGCD(arr, N);
// This code is contributed by shinjanpatra
</script>
Producción:
Player 1
Complejidad de tiempo: (N * sqrt(X)), donde X es el elemento más grande de la array
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por vaibhavsingh19750nit y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA