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 factor (except for 1 & the number itself). The player who is unable to make a move looses the game. Find the winner of the game if A starts the game and both play optimally.
 
Example 1:
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. 
Example 2:
Input: nums = [2, 4, 7, 11]
Outptut: 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.  
Your Task:
You don't need to read or print anything. Your task is to complete the function brainGame() which takes the list of numbers as input parameter and returns true if A wins and false if B wins.
 
Expected Time Complexity: O(N^{2})
Expected Space Complexity: O(N)
 
Constraints
1 <= N <= 1000
1 <= nums[i] <= 1000

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Combinatorics

Mathematics

Starter code: #User function Template for python3



class Solution:

	def brainGame(self, nums):

		# Code here

Solutions:
class Solution:

	def brainGame(self, nums):
		x = [0] * 1005
		for i in range(2, 1001):
			for j in range(2 * i, 1001, i):
				x[j] = max(x[j], 1 + x[i])
		b = 0
		for i in range(len(nums)):
			b = b ^ x[nums[i]]
		if b == 0:
			return False
		return True


class Solution:

	def brainGame(self, nums):
		from math import sqrt, floor
		from collections import defaultdict
		from functools import reduce
		primes = [True] * 1001
		primes[0] = primes[1] = False
		for i in range(floor(sqrt(1000)) + 1):
			if not primes[i]:
				continue
			for j in range(i * i, 1001, i):
				primes[j] = False
		pvs = [i for (i, t) in enumerate(primes) if t]
		cnts = defaultdict(int)
		for v in nums:
			if primes[v]:
				continue
			cnt = 0
			for p in pvs:
				if p > v:
					break
				while v % p == 0:
					cnt += 1
					v //= p
			if cnt > 1:
				cnts[cnt - 1] += 1
		seq = [k for (k, v) in cnts.items() if v % 2 == 1]
		return True if reduce(lambda su, a: su ^ a, seq, 0) else False


import math

class Solution:

	def brainGame(self, nums):

		def Primefacto(n):
			if n <= 1:
				return 0
			ans = 0
			div = 2
			while n > 1:
				if n % div == 0:
					ans += 1
					n = n // div
				else:
					div += 1
			return ans - 1
		arr = [Primefacto(num) for num in nums]
		s = 0
		for i in arr:
			s ^= i
		if s != 0:
			return True
		else:
			return False


class Solution:

	def brainGame(self, nums):
		ans = [0] * 1001
		for i in range(2, 1001):
			for j in range(2 * i, 1001, i):
				ans[j] = max(ans[j], 1 + ans[i])
		res = 0
		for i in range(len(nums)):
			res = res ^ ans[nums[i]]
		if res == 0:
			return False
		return True


class Solution:

	def brainGame(self, nums):
		d = [0] * 1001
		for i in range(2, 1001):
			j = 2 * i
			while j <= 1000:
				d[j] = max(d[j], 1 + d[i])
				j += i
		x = 0
		for i in nums:
			x = x ^ d[i]
		if x == 0:
			return False
		else:
			return True


from math import sqrt

class Solution:

	def brainGame(self, nums):
		ar = [0] * 1001
		for i in range(2, 1001):
			for j in range(2 * i, 1001, i):
				ar[j] = max(ar[j], 1 + ar[i])
		l = 0
		for k in range(len(nums)):
			l = l ^ ar[nums[k]]
		if l == 0:
			return False
		else:
			return True


import math

def prime(num):
	for i in range(2, int(num / 2)):
		if num % i == 0:
			return False
	return True

def primenumbers(n):
	if n <= 1:
		return 0
	ans = 0
	div = 2
	while n > 1:
		if n % div == 0:
			ans += 1
			n = n // div
		else:
			div += 1
	return ans - 1

class Solution:

	def brainGame(self, nums):
		ans = 0
		for i in nums:
			ans ^= primenumbers(i)
		if ans != 0:
			return True
		else:
			return False


from functools import reduce

class Solution:

	def brainGame(self, nums):

		def calcFactorNum(num):
			ans = 0
			if num <= 3:
				return 0
			i = 2
			while num > 1:
				if num % i == 0:
					ans += 1
					num = num // i
				else:
					i += 1
			return ans - 1
		factors = [calcFactorNum(num) for num in nums]
		ans = reduce(lambda x, y: y ^ x, factors)
		if ans == 0:
			return False
		return True


def factors(n):
	prime = [-1 for i in range(n + 1)]
	i = 2
	while i * i <= n:
		if prime[i] == -1:
			for j in range(i * i, n + 1, i):
				if prime[j] == -1:
					prime[j] = i
		i += 1
	x = n
	count = 0
	while prime[x] != -1:
		count += 1
		x = x // prime[x]
	return count

class Solution:

	def brainGame(self, nums):
		c = 0
		for x in nums:
			c = c ^ factors(x)
		if c == 0:
			return False
		else:
			return True


class Solution:

	def brainGame(self, nums):
		a = [0] * 1001
		for i in range(2, 1001):
			for j in range(2 * i, 1001, i):
				a[j] = max(a[j], 1 + a[i])
		z = 0
		for i in range(len(nums)):
			z ^= a[nums[i]]
		return z != 0


from math import sqrt

def isPrime(n):
	i = 2
	while i <= sqrt(n):
		if n % i == 0:
			return False
		i += 1
	return True

def primefactors(n):
	count = 0
	num = n
	i = 2
	while i <= num // 2:
		while n % i == 0:
			count += 1
			n = n // i
		i += 1
	return count

class Solution:

	def brainGame(self, nums):
		val = 0
		for x in nums:
			if isPrime(x) == False:
				val = val ^ primefactors(x) - 1
		if val == 0:
			return False
		else:
			return True


import math

class Solution:

	def brainGame(self, nums):

		def Primefacto(n):
			if n <= 1:
				return 0
			ans = 0
			div = 2
			while n > 1:
				if n % div == 0:
					ans += 1
					n = n // div
				else:
					div += 1
			return ans - 1
		arr = [Primefacto(num) for num in nums]
		s = 0
		for i in arr:
			s ^= i
		if s != 0:
			return True
		else:
			return False

	def prime(self, n):
		d = [0] * (n + 1)
		for i in range(3, n + 1):
			if d[i] == 0:
				for j in range(i * i, n + 1, i):
					d[j] = 1
		se = set()
		for i in range(2, len(d)):
			if d[i] == 0:
				se.add(i)
		return se


class Solution:

	def brainGame(self, a):

		def prime_factors(n):
			i = 2
			factors = {}
			while i * i <= n:
				if n % i:
					i += 1
				else:
					n //= i
					factors[i] = factors.get(i, 0) + 1
			if n > 1:
				factors[n] = factors.get(n, 0) + 1
			return factors
		c = 0
		for i in a:
			if i > 1:
				x = prime_factors(i)
				c1 = 0
				for j in x.keys():
					c1 += x[j]
				c1 -= 1
				c ^= c1
		return c != 0


class Solution:

	def brainGame(self, nums):

		def isPrime(num):
			i = 2
			while i <= num // i:
				if num % i == 0:
					return False
				i += 1
			return True

		def primeFactor(n):
			ans = 0
			num = n
			for i in range(2, num // 2 + 1):
				while n % i == 0:
					ans += 1
					n //= i
			return ans
		ans = 0
		for i in nums:
			if not isPrime(i):
				ans = ans ^ primeFactor(i) - 1
		return ans != 0


import math

class Solution:

	def brainGame(self, nums):
		m1 = max(nums) + 1
		arr1 = [0 for i in range(m1)]
		for i in range(2, m1):
			for j in range(2 * i, m1, i):
				arr1[j] = max(arr1[j], 1 + arr1[i])
		d = {}
		for i in nums:
			if arr1[i] in d:
				del d[arr1[i]]
			else:
				d[arr1[i]] = 1
		ans = 0
		for i in d.keys():
			ans = ans ^ i
		if ans == 0:
			return False
		return True


class Solution:

	def brainGame(self, nums):

		def pf(n):
			if n <= 1:
				return 0
			ans = 0
			div = 2
			while n > 1:
				if n % div == 0:
					ans += 1
					n = n // div
				else:
					div += 1
			return ans - 1
		a = [pf(num) for num in nums]
		s = 0
		for i in a:
			s ^= i
		if s != 0:
			return True
		else:
			return False


class Solution:

	def brainGame(self, nums):

		def steveoferosthethonas(nums):
			L = [True for i in range(nums + 1)]
			(L[0], L[1]) = (False, False)
			i = 2
			while i * i <= nums:
				if L[i] == True:
					j = 2 * i
					while j <= nums:
						L[j] = False
						j += i
				i += 1
			LL = []
			for i in range(len(L)):
				if L[i] == True:
					LL.append(i)
			return LL

		def primefact(nums):
			count = 0
			if nums in l or nums == 1:
				return 1
			while nums != 1:
				for i in l:
					while nums % i == 0:
						nums //= i
						count += 1
					if nums == 1:
						break
			return count
		summ = 0
		l = steveoferosthethonas(max(nums) + 1)
		for i in nums:
			summ = summ ^ primefact(i) - 1
		if summ == 0:
			return 0
		else:
			return 1


def get_primes(n):
	arr = [1] * (n + 1)
	arr[0] = arr[1] = 0
	for i in range(2, n + 1):
		if arr[i]:
			for j in range(i * i, n + 1, i):
				arr[j] = 0
	return set([i for i in range(n + 1) if arr[i]])
primes = get_primes(10 ** 3)

def factorise(n):
	if n < 2:
		return 0
	ans = 0
	d = 2
	while n > 1:
		if n % d == 0:
			ans += 1
			n //= d
		else:
			d += 1
	return ans - 1

class Solution:

	def brainGame(self, nums):
		arr = nums
		n = len(arr)
		l1 = [factorise(i) for i in arr]
		ans = 0
		for i in l1:
			ans ^= i
		return ans != 0


import math

class Solution:

	def brainGame(self, nums):
		m = max(nums) + 1
		arr = [0 for i in range(m)]
		for i in range(2, m):
			for j in range(2 * i, m, i):
				arr[j] = max(arr[j], 1 + arr[i])
		ans = 0
		for i in nums:
			ans = ans ^ arr[i]
		if ans == 0:
			return False
		return True


class Solution:

	def brainGame(self, nums):

		def primeno(n):
			if n <= 1:
				return 0
			a = 0
			d = 2
			while n > 1:
				if n % d == 0:
					a += 1
					n = n // d
				else:
					d += 1
			return a - 1
		ans = []
		for i in nums:
			ans.append(primeno(i))
		s = 0
		for i in ans:
			s ^= i
		if s == 0:
			return False
		return True


class Solution:

	def brainGame(self, nums):

		def primefactors(n):
			if n <= 1:
				return 0
			ans = 0
			div = 2
			while n > 1:
				if n % div == 0:
					ans += 1
					n = n // div
				else:
					div += 1
			return ans - 1
		arr = [primefactors(n) for n in nums]
		k = 0
		for i in arr:
			k ^= i
		if k != 0:
			return True
		else:
			return False


class Solution:

	def p(self, n):
		if n <= 1:
			return 0
		r = 0
		i = 2
		while n > 1:
			if n % i == 0:
				r = r + 1
				n = int(n / i)
			else:
				i += 1
		return r - 1

	def brainGame(self, nums):
		d = [self.p(n) for n in nums]
		r = 0
		for i in d:
			r = r ^ i
		if r != 0:
			return True
		return False


class Solution:

	def brainGame(self, nums):

		def get_total_prime_facts(n):
			if n <= 1:
				return 0
			count = 0
			c = 2
			while n > 1:
				if n % c == 0:
					count += 1
					n = n // c
				else:
					c += 1
			return count - 1
		winner = 0
		for num in nums:
			winner ^= get_total_prime_facts(num)
		return winner != 0


class Solution:

	def brainGame(self, nums):

		def get_total_prime_facts(n):
			if n <= 1:
				return 0
			count = 0
			c = 2
			while n > 1:
				if n % c == 0:
					count += 1
					n = n // c
				else:
					c += 1
			return count - 1
		arr = [get_total_prime_facts(num) for num in nums]
		s = 0
		for i in arr:
			s ^= i
		if s != 0:
			return True
		else:
			return False


class Solution:

	def brainGame(self, nums):
		ls = [0] * 1005
		temp = 0
		for i in range(2, 1001):
			for j in range(2 * i, 1001, i):
				ls[j] = max(ls[i] + 1, ls[j])
		for i in range(len(nums)):
			temp = temp ^ ls[nums[i]]
		return False if temp == 0 else True


class Solution:

	def isprime(self, val):
		for i in range(2, val):
			if val % i == 0:
				return False
		return True

	def prime_factor(self, val):
		ans = 0
		v = val
		for i in range(2, val // 2 + 1):
			while v % i == 0:
				ans += 1
				v //= i
		return ans

	def brainGame(self, nums):
		count = 0
		for i in range(len(nums)):
			if not self.isprime(nums[i]):
				count ^= self.prime_factor(nums[i]) - 1
		return count != 0


class Solution:

	def brainGame(self, nums):
		maxnum = max(nums)
		sieve = {}
		for i in range(2, maxnum + 1):
			sieve[i] = True
		for i in range(2, maxnum + 1):
			num = 0
			if sieve[i]:
				num = i * i
			else:
				continue
			while num <= maxnum:
				sieve[num] = False
				num += i
		npcnt = 0
		for n in nums:
			if n == 1:
				continue
			if sieve[n] == False:
				num = n
				div = 2
				cnt = 0
				while num > 1:
					if num % div == 0:
						num = num // div
						cnt += 1
					else:
						div += 1
				cnt -= 1
				npcnt ^= cnt
		return npcnt > 0


class Solution:

	def brainGame(self, nums):
		max_val = max(nums)
		dp = [0] * (max_val + 1)

		def total_primefactors(num):
			count = 0
			value = num
			i = 2
			while i < value:
				if num % i == 0 and dp[i] == 0:
					num = num / i
					count += 1
					i -= 1
				i += 1
			return count
		for num in range(max(nums) + 1):
			dp[num] = total_primefactors(num)
		for i in range(len(dp)):
			if dp[i]:
				dp[i] -= 1
		ans = 0
		for i in range(len(nums)):
			ans = ans ^ dp[nums[i]]
		if ans:
			return True
		else:
			return False


class Solution:

	def brainGame(self, nums):

		def Primefactor(n):
			if n <= 1:
				return 0
			ans = 0
			div = 2
			while n > 1:
				if n % div == 0:
					ans += 1
					n = n // div
				else:
					div += 1
			return ans - 1
		arr = [Primefactor(num) for num in nums]
		s = 0
		for i in arr:
			s ^= i
		return s != 0


class Solution:

	def brainGame(self, nums):
		factor = [0] * 1001

		def cal(n):
			prime = [1 for i in range(n + 1)]
			p = 2
			while p * p <= n:
				if prime[p] == 1:
					for i in range(p * p, n + 1, p):
						prime[i] = 0
				p += 1
			return prime
		prime = cal(1000)

		def primefactor(n):
			if n == 1:
				return 1
			count = 0
			c = 2
			while n > 1:
				if n % c == 0:
					count += 1
					n //= c
				else:
					c += 1
			return count
		new = [primefactor(n) - 1 for n in nums]
		ans = 0
		for i in new:
			ans = ans ^ i
		if ans != 0:
			return True
		return False


class Solution:

	def brainGame(self, nums):

		def primes(nums):
			if nums <= 1:
				return 0
			ans = 0
			div = 2
			while nums > 1:
				if nums % div == 0:
					ans += 1
					nums = nums // div
				else:
					div += 1
			return ans - 1
		arr = [primes(num) for num in nums]
		cnt = 0
		for x in arr:
			cnt ^= x
		if cnt != 0:
			return True
		else:
			return False


class Solution:

	def brainGame(self, nums):
		A = [0 for i in range(1001)]
		for i in range(2, 1001):
			for j in range(2 * i, 1001, i):
				A[j] = max(A[j], A[i] + 1)
		x = 0
		for i in range(len(nums)):
			x = x ^ A[nums[i]]
		if x == 0:
			return False
		else:
			return True