Winning Game by replacing numbers with factors (Brain Game)
Given 2 players A and B take turns alternatively to play a game in which they have N numbers on a paper. In one turn, a player can replace one of the numbers by any of its factors (except for 1 & the number itself). The player who is unable to make a move loses the game. Find the winner of the game if A starts the game and both play optimally.
Examples:
Input: nums = [5, 7, 3]
Output: B
Explanation: Since all the numbers are prime, so A will not be able to make the first move.Input: nums = [2, 4, 7, 11]
Output: A
Explanation: In the first move A will replace 4 by 2, so the numbers will become [2, 2, 7, 11] now B will not be able to make a move since all the remaining numbers can only be divided by 1 or the number itself.
Approach: To solve the problem, follow the below idea:
In a game where all numbers are prime, Player A loses. If there’s only one composite number, Player A wins by replacing it with its prime factors. If there are two composite numbers with equal prime factors, Player A loses in optimal play. If the prime factors are unequal, Player A wins by choosing the number with more factors and matching the count. In general, if there are at least two numbers with unequal prime factors, Player A wins; otherwise, Player B wins.
Step-by-step algorithm:
- To calculate the number of prime factors of each number we can run a loop for each number. Following are the steps to find the number of prime factors. Let the number be n and Initialize the count of prime factors for each number as 0, While n is divisible by 2, add the number of times it is divided by 2 to the count and divide n by 2.
- After step 1, n must be odd. Now start a loop from i = 3 to the square root of n. While i divides n, add number of times that the number is divided to count and divide n by i. After i fails to divide n, increment i by 2 and continue. If n is a prime number and is greater than 2, then n will not become 1 by the above two steps. So add 1 to the count.
- After finding the number of prime factors of each number we will store in an array and we will find the XOR value of all the numbers which we stored.
- If the XOR value is zero that means, there are no 2 numbers which have different count of prime factors.
- If the XOR is value is not zero, then Player A wins otherwise Player B wins.
Below is the implementation of the algorithm:
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
// Function to check whether the number is prime or
// not
bool isPrime(int n)
{
// Corner cases
if (n <= 1)
return false;
if (n <= 3)
return true;
// This is checked so that we can skip
// middle five numbers in below loop
if (n % 2 == 0 || n % 3 == 0)
return false;
// Using concept of prime number
// can be represented in form of
// (6*n + 1) or(6*n - 1) hence
// we have to go for every multiple of 6 and
// prime number would always be 1 less or 1 more then
// the multiple of 6.
for (int i = 5; i * i <= n; i = i + 6)
if (n % i == 0 || n % (i + 2) == 0)
return false;
return true;
}
int primeFactors(int n)
{
// to store the count of prime factors
int ans = 0;
// Print the number of 2s that divide n
while (n % 2 == 0) {
ans++;
n = n / 2;
}
// n must be odd at this point. So we can skip
// one element (Note i = i +2)
for (int i = 3; i <= sqrt(n); i = i + 2) {
// While i divides n, print i and divide n
while (n % i == 0) {
ans++;
n = n / i;
}
}
// This condition is to handle the case when n
// is a prime number greater than 2
if (n > 2)
ans++;
return ans;
}
// Function to find which player will
// win
bool brainGame(vector<int> nums)
{
vector<int> a(1005, 0);
for (int i = 2; i <= 1000; i++) {
if (!isPrime(i)) {
a[i] = primeFactors(i) - 1;
}
}
int x = 0;
for (int i = 0; i < nums.size(); i++) {
x = x ^ a[nums[i]];
}
if (x == 0)
return false;
return true;
}
// Driver code
int main()
{
int n = 5;
vector<int> nums = { 1, 4, 3, 4, 5 };
// Function call
if (brainGame(nums)) {
cout << "A";
}
else {
cout << "B";
}
return 0;
}
import java.util.*;
public class Main {
// Function to check whether the number is prime or not
static boolean isPrime(int n) {
// Corner cases
if (n <= 1)
return false;
if (n <= 3)
return true;
// This is checked so that we can skip
// middle five numbers in below loop
if (n % 2 == 0 || n % 3 == 0)
return false;
// Using the concept of a prime number
// can be represented in the form of
// (6 * n + 1) or (6 * n - 1) hence
// we have to go for every multiple of 6 and
// prime number would always be 1 less or 1 more than
// the multiple of 6.
for (int i = 5; i * i <= n; i = i + 6)
if (n % i == 0 || n % (i + 2) == 0)
return false;
return true;
}
static int primeFactors(int n) {
// to store the count of prime factors
int ans = 0;
// Print the number of 2s that divide n
while (n % 2 == 0) {
ans++;
n = n / 2;
}
// n must be odd at this point. So we can skip
// one element (Note i = i + 2)
for (int i = 3; i <= Math.sqrt(n); i = i + 2) {
// While i divides n, print i and divide n
while (n % i == 0) {
ans++;
n = n / i;
}
}
// This condition is to handle the case when n
// is a prime number greater than 2
if (n > 2)
ans++;
return ans;
}
// Function to find which player will win
static boolean brainGame(ArrayList<Integer> nums) {
ArrayList<Integer> a = new ArrayList<>(Collections.nCopies(1005, 0));
for (int i = 2; i <= 1000; i++) {
if (!isPrime(i)) {
a.set(i, primeFactors(i) - 1);
}
}
int x = 0;
for (int i = 0; i < nums.size(); i++) {
x = x ^ a.get(nums.get(i));
}
return x != 0;
}
// Driver code
public static void main(String[] args) {
int n = 5;
ArrayList<Integer> nums = new ArrayList<>(Arrays.asList(1, 4, 3, 4, 5));
// Function call
if (brainGame(nums)) {
System.out.println("A");
} else {
System.out.println("B");
}
}
}
# Python Implementation
import math
# Function to check whether the number is prime or not
def is_prime(n):
if n <= 1:
return False
if n <= 3:
return True
if n % 2 == 0 or n % 3 == 0:
return False
for i in range(5, int(math.sqrt(n)) + 1, 6):
if n % i == 0 or n % (i + 2) == 0:
return False
return True
# Function to calculate the number of prime factors
def prime_factors(n):
ans = 0
while n % 2 == 0:
ans += 1
n = n // 2
for i in range(3, int(math.sqrt(n)) + 1, 2):
while n % i == 0:
ans += 1
n = n // i
if n > 2:
ans += 1
return ans
# Function to determine which player will win
def brain_game(nums):
a = [0] * 1005
# Pre-compute the prime factors for numbers from 2 to 1000
for i in range(2, 1001):
if not is_prime(i):
a[i] = prime_factors(i) - 1
x = 0
# Calculate XOR of prime factors for each number in nums
for num in nums:
x = x ^ a[num]
# If XOR result is 0, player B wins; otherwise, player A wins
if x == 0:
return False
return True
# Main function
n = 5
nums = [1, 4, 3, 4, 5]
# Check the winner and print the result
if brain_game(nums):
print("A")
else:
print("B")
# This code is contributed by Tapesh(tapeshdu420)
using System;
using System.Collections.Generic;
public class MainClass {
// Function to check whether the number is prime or not
static bool IsPrime(int n)
{
// Corner cases
if (n <= 1)
return false;
if (n <= 3)
return true;
// This is checked so that we can skip middle five
// numbers in below loop
if (n % 2 == 0 || n % 3 == 0)
return false;
// Using concept of prime number can be represented
// in form of (6 * n + 1) or (6 * n - 1) hence we
// have to go for every multiple of 6 and prime
// number would always be 1 less or 1 more than the
// multiple of 6.
for (int i = 5; i * i <= n; i = i + 6)
if (n % i == 0 || n % (i + 2) == 0)
return false;
return true;
}
// Function to count prime factors of a number
static int PrimeFactors(int n)
{
// to store the count of prime factors
int ans = 0;
// Print the number of 2s that divide n
while (n % 2 == 0) {
ans++;
n = n / 2;
}
// n must be odd at this point. So we can skip one
// element (Note i = i + 2)
for (int i = 3; i <= Math.Sqrt(n); i = i + 2) {
// While i divides n, print i and divide n
while (n % i == 0) {
ans++;
n = n / i;
}
}
// This condition is to handle the case when n is a
// prime number greater than 2
if (n > 2)
ans++;
return ans;
}
// Function to find which player will win
static bool BrainGame(List<int> nums)
{
int[] a = new int[1005];
for (int i = 2; i <= 1000; i++) {
if (!IsPrime(i)) {
a[i] = PrimeFactors(i) - 1;
}
}
int x = 0;
foreach(int num in nums) { x ^= a[num]; }
return x != 0;
}
// Driver code
public static void Main(string[] args)
{
List<int> nums = new List<int>{ 1, 4, 3, 4, 5 };
// Function call
if (BrainGame(nums)) {
Console.WriteLine("A");
}
else {
Console.WriteLine("B");
}
}
}
// Function to check whether the number is prime or not
function isPrime(n) {
// Corner cases
if (n <= 1)
return false;
if (n <= 3)
return true;
// This is checked so that we can skip
// middle five numbers in below loop
if (n % 2 === 0 || n % 3 === 0)
return false;
// Using the concept of prime number
// can be represented in the form of
// (6 * n + 1) or (6 * n - 1) hence
// we have to go for every multiple of 6 and
// the prime number would always be 1 less or 1 more than
// the multiple of 6.
for (let i = 5; i * i <= n; i = i + 6)
if (n % i === 0 || n % (i + 2) === 0)
return false;
return true;
}
// Function to count prime factors
function primeFactors(n) {
// to store the count of prime factors
let ans = 0;
// Print the number of 2s that divide n
while (n % 2 === 0) {
ans++;
n = Math.floor(n / 2);
}
// n must be odd at this point. So we can skip
// one element (Note i = i +2)
for (let i = 3; i <= Math.sqrt(n); i = i + 2) {
// While i divides n, print i and divide n
while (n % i === 0) {
ans++;
n = Math.floor(n / i);
}
}
// This condition is to handle the case when n
// is a prime number greater than 2
if (n > 2)
ans++;
return ans;
}
// Function to find which player will win
function brainGame(nums) {
let a = new Array(1005).fill(0);
for (let i = 2; i <= 1000; i++) {
if (!isPrime(i)) {
a[i] = primeFactors(i) - 1;
}
}
let x = 0;
for (let i = 0; i < nums.length; i++) {
x = x ^ a[nums[i]];
}
if (x === 0)
return false;
return true;
}
// Driver code
function main() {
let nums = [1, 4, 3, 4, 5];
// Function call
if (brainGame(nums)) {
console.log("A");
} else {
console.log("B");
}
}
// Call the main function
main();
//This code is contributed by utkarsh
Output
B
Time Complexity: O(N*sqrt(N)*logN)
Auxiliary Space: O(N)
Approach: Nim Game Theory with Precomputed Prime Factor Counts
This problem can be reduced to a form of a Nim game, where each number on the paper can be thought of as a pile of stones, and the moves correspond to reducing these piles by certain allowed moves (removing factors). We use game theory to decide the winner if both players play optimally. Each number’s moves are determined by its prime factor count, as transforming a number into one of its factors effectively reduces its “pile” size. The key insight here is that if a number has no prime factors other than itself (i.e., it is a prime number), then no moves can be made with that number. Thus, for gameplay purposes, these numbers are like piles of size zero in Nim—they do not affect the outcome. We simplify the problem by precomputing the counts of prime factors for all numbers up to the maximum possible value in the list, and then use the theory of Nim sums (XOR of pile sizes) to determine the winner.
Steps:
- Precomputation: Compute the count of prime factors for all numbers up to a reasonable limit, adjusting for the problem’s constraints.
- Game State Representation: Treat each number’s prime factor count (minus one, to exclude the number itself) as its pile size in a Nim game.
- Nim Sum Calculation: Calculate the XOR of all pile sizes. If the result is non-zero, the starting player (Player A) has a winning strategy; otherwise, Player B will win.
#include <algorithm>
#include <iostream>
#include <vector>
std::vector<int> sievePrimeFactors(int limit)
{
std::vector<int> factors(limit + 1, 0);
for (int i = 2; i <= limit; ++i) {
if (factors[i] == 0) { // i is prime
for (int j = i; j <= limit; j += i) {
int k = j;
while (k % i == 0) {
factors[j]++;
k /= i;
}
}
}
}
return factors;
}
char canPlayerWin(std::vector<int>& nums)
{
int maxValue
= *std::max_element(nums.begin(), nums.end());
std::vector<int> primeFactorsCount
= sievePrimeFactors(maxValue);
int nimSum = 0;
for (int num : nums) {
if (primeFactorsCount[num] > 1) {
nimSum ^= (primeFactorsCount[num] - 1);
}
}
return (nimSum != 0) ? 'A' : 'B';
}
int main()
{
std::vector<int> nums = { 1, 4, 3, 4, 5 };
std::cout << canPlayerWin(nums)
<< std::endl; // Output: B
return 0;
}
import java.util.ArrayList;
import java.util.Collections;
public class Main {
// Function to calculate the number of prime factors for
// each number up to the limit
public static ArrayList<Integer>
sievePrimeFactors(int limit)
{
// Initialize an array list to store the number of
// prime factors for each number
ArrayList<Integer> factors = new ArrayList<>(
Collections.nCopies(limit + 1, 0));
// Loop through each number starting from 2
// (smallest prime number)
for (int i = 2; i <= limit; ++i) {
// If the number is prime (its count in factors
// is 0)
if (factors.get(i) == 0) {
// Mark its multiples
for (int j = i; j <= limit; j += i) {
int k = j;
// Count the number of times the prime
// factor divides the number
while (k % i == 0) {
factors.set(j, factors.get(j) + 1);
k /= i;
}
}
}
}
return factors;
}
// Function to determine the winner of the game based on
// the given numbers
public static char canPlayerWin(ArrayList<Integer> nums)
{
// Find the maximum value in the list to set the
// limit for the sieve function
int maxValue = Collections.max(nums);
// Get the prime factors count for all numbers up to
// the maximum value
ArrayList<Integer> primeFactorsCount
= sievePrimeFactors(maxValue);
// Calculate the Nim sum
int nimSum = 0;
for (int num : nums) {
// Consider only the counts greater than 1,
// subtract 1 to adjust the game logic
if (primeFactorsCount.get(num) > 1) {
nimSum ^= (primeFactorsCount.get(num) - 1);
}
}
// If nimSum is non-zero, player A wins, otherwise
// player B wins
return (nimSum != 0) ? 'A' : 'B';
}
public static void main(String[] args)
{
// Initialize the list of numbers
ArrayList<Integer> nums = new ArrayList<>();
Collections.addAll(nums, 1, 4, 3, 4, 5);
// Print the winner of the game
System.out.println(canPlayerWin(nums)); // Output: B
}
}
def sieve_prime_factors(limit):
factors = [0] * (limit + 1)
for i in range(2, limit + 1):
if factors[i] == 0: # i is prime
for j in range(i, limit + 1, i):
k = j
while k % i == 0:
factors[j] += 1
k //= i
return factors
def can_player_a_win(nums):
MAX_VALUE = max(nums)
prime_factors_count = sieve_prime_factors(MAX_VALUE)
nim_sum = 0
for num in nums:
# Subtract 1 to exclude the number itself from its factors
if prime_factors_count[num] > 1:
nim_sum ^= (prime_factors_count[num] - 1)
return "A" if nim_sum != 0 else "B"
# Example usage
nums = [1, 4, 3, 4, 5 ];
print(can_player_a_win(nums)) # Output: B
// Function to compute the number of prime factors for each number up to the given limit
function sievePrimeFactors(limit) {
let factors = new Array(limit + 1).fill(0);
// Sieve of Eratosthenes modified to count prime factors
for (let i = 2; i <= limit; ++i) {
if (factors[i] === 0) { // i is a prime number
for (let j = i; j <= limit; j += i) {
let k = j;
while (k % i === 0) {
factors[j]++;
k /= i;
}
}
}
}
return factors;
}
// Function to determine the winner of the game based on the given numbers
function canPlayerWin(nums) {
let maxValue = Math.max(...nums); // Find the maximum value in nums
let primeFactorsCount = sievePrimeFactors(maxValue); // Get prime factors count up to
//maxValue
let nimSum = 0;
// Calculate the nim-sum based on the number of prime factors
for (let num of nums) {
if (primeFactorsCount[num] > 1) {
nimSum ^= (primeFactorsCount[num] - 1); // Nim-sum calculation
}
}
// Determine the winner based on nim-sum
return (nimSum !== 0) ? 'A' : 'B';
}
// Example usage
let nums = [1, 4, 3, 4, 5];
console.log(canPlayerWin(nums)); // Output: B
Output
B
Time Complexity: O(N log(log(N))) for sieve precomputation, where N is the upper limit of number values, plus O(M) for evaluating the game outcome, where M is the length of the number list. This is significantly better than the direct factorization for each number individually in terms of scalability.
Auxiliary Space : O(N) due to the sieve array storing prime factor counts up to the highest number in the list.