Two players, Player 1 and Player 2, are given an integer N to play a game. The rules of the game are as follows :
1. In one turn, a player can remove any set bit of N in its binary representation to make a new N.
2. Player 1 always takes first turn.
3. If a player cannot make a move, he loses.
 
Example 1:
Input:
N = 8
Output:
1
Explanation:
N = 8
N = 1000 (binary)
Player 1 takes the bit.
The remaining bits are all zero.
Player 2 cannot make a move, 
so Player 1 wins.
 
 
Example 2:
Input:
N = 1
Output:
1
Explanation:
N = 0001
Player 1 takes one in one 
move, so Player 2 loses.
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function swapBitGame() which takes an integer N and returns "1" if Player 1 wins, else return "2".
 
Expected Time Complexity: O(log(N))
Expected Auxiliary Space: O(1)
 
Constraints : 
1 <= N <= 10^12

Source: geeksforgeeks | Difficulty: EASY
Tags: Bit manipulation

Data structures

Starter code: #User function Template for python3



class Solution:

    def swapBitGame (self,N):

        # code here 

Solutions:
class Solution:

	def swapBitGame(self, N):
		count = 0
		while N:
			if N & 1 == 1:
				count += 1
			N >>= 1
		if count % 2 == 0:
			return 2
		return 1


class Solution:

	def swapBitGame(self, N):
		k = bin(N)[2:]
		if k.count('1') % 2 == 0:
			return '2'
		return '1'


class Solution:

	def swapBitGame(self, N):
		p1 = False
		p2 = False
		while N != 0:
			N = N & N - 1
			if p1:
				p2 = True
				p1 = False
			else:
				p1 = True
				p2 = False
		return 1 if p1 else 2


class Solution:

	def swapBitGame(self, N):
		s = bin(N).replace('0b', '')
		k = s.count('1')
		if k % 2 == 0:
			return 2
		else:
			return 1


class Solution:

	def swapBitGame(self, N):
		ans = 0
		while N > 0:
			ans += N & 1
			N >>= 1
		if ans % 2 == 1:
			return 1
		else:
			return 2


class Solution:

	def swapBitGame(self, N):
		c = bin(N).count('1')
		if c % 2:
			return 1
		return 2


class Solution:

	def swapBitGame(self, N):
		count = sum((item == '1' for item in bin(N)[2:]))
		return 1 if count % 2 else 2


class Solution:

	def swapBitGame(self, n):
		a = ' '
		b = 0
		while n > 0:
			a = a + str(n % 2)
			if n % 2 == 1:
				b = b + 1
			n = n // 2
		if b % 2 == 0:
			return 2
		else:
			return 1


class Solution:

	def swapBitGame(self, N):
		return bin(N).count('1') % 2 or 2


class Solution:

	def swapBitGame(self, N):
		b = bin(N)
		c = b[::-1]
		d = 0
		for i in c:
			if i == '1':
				d = d + 1
			elif i == 'b':
				break
		if d % 2 == 0:
			return 2
		else:
			return 1


class Solution:

	def swapBitGame(self, N):
		n = bin(N)[2:]
		count = n.count('1')
		if count == 1:
			return 1
		if count % 2 != 0:
			return 1
		else:
			return 2


class Solution:

	def swapBitGame(self, N):
		count = 0
		for i in str(bin(N)[2:]):
			if i is '1':
				count += 1
		if count % 2 == 0:
			return 2
		return 1


class Solution:

	def swapBitGame(self, N):
		lis = '{0:b}'.format(N)
		binary = list(map(int, list(lis)))
		if sum(binary) % 2 == 0:
			return 2
		else:
			return 1


import numpy as np

class Solution:

	def swapBitGame(self, N):
		max_bits = int(np.log2(N) + 1)
		bits_taken = 0
		i = 0
		while N > 0:
			minus = int(2 ** (max_bits - 1 - i))
			i += 1
			if N >= minus:
				N -= minus
				bits_taken += 1
		return 2 - bits_taken % 2


class Solution:

	def swapBitGame(self, N):
		n = N
		(b, s) = (0, 0)
		while n > 0:
			m = n % 2
			n = n // 2
			b = m * 10 ** s + b
			s = s + 1
		a = [int(x) for x in str(b)]
		c = a.count(1)
		(p, q) = (0, 0)
		for i in range(0, c):
			if i % 2 == 0:
				p = p + 1
			else:
				q = q + 1
		m = max(p, q)
		if m == p == q:
			return 2
		elif m == p:
			return 1
		elif m == q:
			return 2


class Solution:

	def swapBitGame(self, N):
		b = bin(N)
		c = str(b)
		c = c[2:]
		d = c.count('1')
		if d % 2 == 1:
			return 1
		else:
			return 2


class Solution:

	def swapBitGame(self, N):
		s = ''
		while N != 0:
			s = str(N % 2) + s
			N = N // 2
		l = list(s)
		a = l.count('1')
		if a % 2 != 0:
			return 1
		else:
			return 2


class Solution:

	def swapBitGame(self, N):
		b = bin(N).replace('0b', '')
		count1 = b.count('1')
		if count1 % 2 == 0:
			return 2
		else:
			return 1


class Solution:

	def swapBitGame(self, N):
		ans = str()
		while N >= 1:
			rem = int(N % 2)
			N = N / 2
			ans = ans + str(rem)
		b = ans[::-1]
		count0 = 0
		count1 = 0
		for i in range(len(b)):
			if b[i] == '0':
				count0 += 1
			elif b[i] == '1':
				count1 += 1
		if count1 % 2 != 0:
			return '1'
		else:
			return '2'


class Solution:

	def swapBitGame(self, N):
		if len(bin(N).replace('0b', '').replace('0', '')) % 2 == 0:
			return 2
		return 1


class Solution:

	def swapBitGame(self, N):
		t = bin(N)[2:]
		c = 0
		for i in str(t):
			if i == '1':
				c = c + 1
		if c % 2 == 1:
			return 1
		else:
			return 2


class Solution:

	def swapBitGame(self, N):
		p1 = 0
		p2 = 0
		b = bin(N)
		b = b[2:]
		if b.count('1') & 1 == 1:
			return 1
		return 2


from collections import Counter

class Solution:

	def swapBitGame(self, N):
		bstg = Counter(bin(N).replace('0b', ''))
		if bstg['1'] % 2 == 1:
			return 1
		return 2


class Solution:

	def swapBitGame(self, N):
		if N in range(1, int(1000000000000.0) + 1):
			import math
			b = ''
			c = N
			b = bin(c)[2:]
			n = 0
			p = list(b)
			a1 = 0
			a0 = 0
			for i in p:
				if i == '1':
					a1 = a1 + 1
				else:
					a0 = a0 + 1
			while True:
				n = n + 1
				a1 = a1 - 1
				if a1 == 0:
					break
			if n % 2 == 1:
				answer = 1
			else:
				answer = 2
		return answer


class Solution:

	def swapBitGame(self, N):

		def bitCount(N):
			if N == 0:
				return 0
			return 1 + bitCount(N & N - 1)
		return 1 if bitCount(N) % 2 == 1 else 2


class Solution:

	def swapBitGame(self, N):
		N1 = str(bin(N))
		list1 = list(N1)
		list1.pop(0)
		list1.pop(0)
		ans = list1.count('1')
		if ans % 2 != 0:
			return 1
		else:
			return 2


import math

class Solution:

	def swapBitGame(self, N):
		count = 0
		while N > 0:
			if N % 2 == 1:
				count += 1
			N = N // 2
		if count % 2 == 0:
			return 2
		else:
			return 1


class Solution:

	def swapBitGame(self, N):
		cnt = 0
		while N:
			N = N & N - 1
			cnt += 1
		return 2 - cnt % 2


class Solution:

	def swapBitGame(self, N):
		c = 0
		a = '{0:b}'.format(int(N))
		for i in a:
			if i == '1':
				c += 1
		if c % 2 != 0:
			return 1
		else:
			return 2


class Solution:

	def swapBitGame(self, N):
		b = bin(N)
		b1 = b[2:]
		one = b1.count('1')
		zero = b1.count('0')
		if one % 2 == 0:
			return 2
		return 1


class Solution:

	def swapBitGame(self, N):
		b = bin(N)[2:]
		o = b.count('1')
		if o % 2 == 0:
			return 2
		else:
			return 1


class Solution:

	def swapBitGame(self, N):
		s = bin(N)[2:]
		if str(s).count('1') % 2 == 0:
			return 2
		return 1


class Solution:

	def swapBitGame(self, N):
		x = bin(N).replace('0b', '')
		count = x.count('1')
		if count % 2 == 1:
			return 1
		return 2


class Solution:

	def swapBitGame(self, N):
		val = list(bin(N).replace('0b', ''))
		res = val.count('1')
		if res % 2 == 0:
			return 2
		else:
			return 1


class Solution:

	def swapBitGame(self, N):
		s = '{0:b}'.format(int(N))
		s = str(s)
		c = 0
		for i in s:
			if i == '1':
				c = c + 1
			else:
				pass
		if c % 2 == 0:
			return 2
		else:
			return 1


import math

class Solution:

	def swapBitGame(self, n):
		count = 0
		while n > 0:
			count += 1
			n -= 2 ** math.floor(math.log2(n))
		if count % 2 == 0:
			return 2
		return 1


class Solution:

	def swapBitGame(self, N):
		s = ''
		while N > 1:
			n = N % 2
			N = N // 2
			s += str(n)
		s += '1'
		n = s.count('1')
		if n % 2 == 0:
			return 2
		else:
			return 1


class Solution:

	def swapBitGame(self, N):
		n = bin(N)
		a = str(n).count('1')
		if a % 2 == 0:
			return '2'
		return '1'


class Solution:

	def swapBitGame(self, N):
		b = str(bin(N).lstrip('ob'))
		n = b.count('1')
		if n % 2 != 0:
			return '1'
		else:
			return '2'


class Solution:

	def swapBitGame(self, N):
		c = 0
		for i in range(39, -1, -1):
			k = N >> i
			if k & 1:
				c += 1
		if c % 2 == 0:
			return 2
		return 1


class Solution:

	def swapBitGame(self, N):
		count = 0
		for i in range(64):
			if N >> i & 1 == 1:
				count += 1
		if count % 2 == 0:
			return 2
		return 1


class Solution:

	def swapBitGame(self, N):
		str = []

		def DecimalToBinary(num):
			if num >= 1:
				DecimalToBinary(num // 2)
				str.append(num % 2)

		def countX(lst, x):
			count = 0
			for ele in lst:
				if ele == x:
					count = count + 1
			return count
		DecimalToBinary(N)
		c = countX(str, 1)
		if c % 2 == 0:
			return 2
		else:
			return 1


class Solution:

	def swapBitGame(self, N):
		if str(bin(N).replace('0b', ' ')).count('1') % 2 == 0:
			return 2
		return 1


class Solution:

	def swapBitGame(self, N):
		new_n = bin(N)
		new_n = new_n[2:]
		count = 0
		for i in new_n:
			if i == '1':
				count += 1
		if count % 2 == 1:
			return 1
		else:
			return 2


class Solution:

	def swapBitGame(self, N):
		z = bin(N)[2:]
		s = str(z)
		count = 0
		for i in s:
			if i == '1':
				count += 1
		if count % 2 == 0:
			return 2
		else:
			return 1


class Solution:

	def swapBitGame(self, N):
		num = [x for x in bin(N).replace('0b', '')]
		cnt = num.count('1')
		if cnt % 2 != 0:
			return 1
		else:
			return 2


class Solution:

	def swapBitGame(self, N):
		k = bin(N)
		k = str(k)
		l = k.count('1')
		if l % 2 == 0:
			return 2
		else:
			return 1