Two players, Player 1 and Player 2, are given an integer N to play a game. The rules of the game are as follows :
- In one turn, a player can remove any set bit of N in its binary representation to make a new N.
- Player 1 always takes the first turn.
- If a player cannot make a move, he loses.
Examples:
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.Input: N = 3
Output: 2
Approach: The given problem can be solved by following the below idea:
Calculate the number of set bits in N. If the number of set bits is odd then player 1 will always win [because he will take the following turns – 1st, 3rd, 5th, . . . and any odd turn]. Otherwise, player 2 will win the game.
Follow the steps mentioned below to implement the:
- Calculate the number of set bits in N.
- If the number of the set bits is odd then player 1 wins.
- Else, player 2 wins.
Below is the implementation of the above approach.
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Function to find the winnerint swapBitGame(long long N){ int bitCount = 0; // Calculate the number of set bit in // N using Brian Kernighan's Algorithm while (N) { N = (N & (N - 1)); bitCount++; } // If bitCount is even return 2 // else return 1 return bitCount % 2 == 0 ? 2 : 1;}// Driver Codeint main(){ long long N = 8; // Function Call cout << swapBitGame(N) << endl; return 0;} |
Java
// Java code to implement the approachimport java.io.*;class GFG { // Function to find the winner static int swapBitGame(long N) { int bitCount = 0; // Calculate the number of set bit in // N using Brian Kernighan's Algorithm while (N!=0) { N = (N & (N - 1)); bitCount++; } // If bitCount is even return 2 // else return 1 return bitCount % 2 == 0 ? 2 : 1; } public static void main(String[] args) { long N = 8; // Function call System.out.println(swapBitGame(N)); }}// This code is contributed by lokeshmvs21. |
Python
# Python code to implement the approach# Function to find the winnerdef swapBitGame(N): bitCount = 0 # Calculate the number of set bit in # N using Brian Kernighan's Algorithm while (N > 0): N = (N & (N - 1)) bitCount += 1 # If bitCount is even return 2 # else return 1 return (2) if bitCount % 2 == 0 else (1)# Driver CodeN = 8#Function Callprint(swapBitGame(N))# This code is contributed by Samim Hossain Mondal. |
C#
// C# code to implement the approachusing System;public class GFG { // Function to find the winner static int swapBitGame(long N) { int bitCount = 0; // Calculate the number of set bit in // N using Brian Kernighan's Algorithm while (N != 0) { N = (N & (N - 1)); bitCount++; } // If bitCount is even return 2 // else return 1 return bitCount % 2 == 0 ? 2 : 1; } static public void Main() { // Code long N = 8; // Function call Console.WriteLine(swapBitGame(N)); }}// This code is contributed by lokesh. |
Javascript
// JavaScript code to implement the approach// Function to find the winnerconst swapBitGame = (N) => { let bitCount = 0; // Calculate the number of set bit in // N using Brian Kernighan's Algorithm while (N) { N = (N & (N - 1)); bitCount++; } // If bitCount is even return 2 // else return 1 return bitCount % 2 == 0 ? 2 : 1;}// Driver Codelet N = 8;// Function Callconsole.log(swapBitGame(N));// This code is contributed by rakeshsahni. |
Output
1
Time Complexity: O(log N)
Auxiliary Space: O(1)
Approach: Naive Recursion with memoization
Steps:
- First, check if the solution for the given input N is already present in the memoization map.
- If it is present, then return the value of the solution from the map to avoid recalculation.
- If it is not present, use a loop to iterate through all the bits of N.
- Remove the set bit by using the XOR operation.
- Then recursively call the solve function for the new value of N.
- After the recursive call, we use the OR operation to set the bit back to the original value of N.
- Check if the returned solution from the recursive call is Player 2 losing or not. If it is Player 2 losing.
- update the memoization map with the solution and return Player 1 wins.
- If we have iterated through all the bits of N and Player 2 has not lost.
- update the memoization map with Player 2 winning and return Player 2 wins.
- Finally, print the result.
Below is the code implementation of the above approach:
C++
// C++ program for the above problem using Naive Recursion with Memoization approach#include<bits/stdc++.h>using namespace std;// Memoization tableunordered_map<int, int> memo;// Recursive functionint solve(int n){ // Base case if(n==0) return 2; if(memo.find(n) != memo.end()) return memo[n]; int ans = 0; for(int i=0; i<31; i++){ if(n & (1<<i)){ n ^= (1<<i); ans = solve(n); n |= (1<<i); // If Player 1 wins in the current subproblem, then Player 2 will lose, so return 1. if(ans==2) { memo[n] = 1; return 1; } } } // If Player 1 cannot make any move, then Player 2 wins. memo[n] = 2; return 2;}// Driver codeint main(){ int n=8; int res = solve(n); if(res==1) cout << "1"; else cout << "2"; return 0;} |
Java
// Java codeimport java.io.*;import java.util.HashMap;import java.util.Map;public class GFG { // Memoization table static Map<Integer, Integer> memo = new HashMap<>(); // Recursive function static int solve(int n) { // Base case if (n == 0) return 2; if (memo.containsKey(n)) return memo.get(n); int ans = 0; for (int i = 0; i < 31; i++) { if ((n & (1 << i)) != 0) { n ^= (1 << i); ans = solve(n); n |= (1 << i); // If Player 1 wins in the current subproblem, // then Player 2 will lose, so return 1. if (ans == 2) { memo.put(n, 1); return 1; } } } // If Player 1 cannot make any move, then Player 2 wins. memo.put(n, 2); return 2; } // Driver code public static void main(String[] args) { int n = 8; int res = solve(n); if (res == 1) { System.out.println("1"); } else { System.out.println("2"); } }}// This code is contributed by guptapratik |
Python3
import sys# Memoization tablememo = {}# Recursive functiondef solve(n): # Base case if n == 0: return 2 if n in memo: return memo[n] ans = 0 for i in range(31): if n & (1 << i): n ^= (1 << i) ans = solve(n) n |= (1 << i) # If Player 1 wins in the current subproblem, # then Player 2 will lose, so return 1. if ans == 2: memo[n] = 1 return 1 # If Player 1 cannot make any move, then Player 2 wins. memo[n] = 2 return 2# Test casen = 8res = solve(n)if res == 1: print("1")else: print("2")sys.exit(0) |
C#
using System;using System.Collections.Generic;class Program{ // Memoization table static Dictionary<int, int> memo = new Dictionary<int, int>(); // Recursive function static int Solve(int n) { // Base case if (n == 0) return 2; if (memo.ContainsKey(n)) return memo[n]; int ans = 0; for (int i = 0; i < 31; i++) { if ((n & (1 << i)) != 0) { n ^= (1 << i); ans = Solve(n); // If Player 1 wins in the current subproblem, then Player 2 will lose, so return 1. if (ans == 2) { memo[n] = 1; return 1; } n |= (1 << i); } } // If Player 1 cannot make any move, then Player 2 wins. memo[n] = 2; return 2; } // Driver code static void Main() { int n = 8; int res = Solve(n); if (res == 1) Console.WriteLine("1"); else Console.WriteLine("2"); }} |
Javascript
// Memoization tableconst memo = new Map();// Recursive functionfunction solve(n) { // Base case if (n === 0) return 2; if (memo.has(n)) return memo.get(n); let ans = 0; for (let i = 0; i < 31; i++) { if (n & (1 << i)) { n ^= (1 << i); ans = solve(n); n |= (1 << i); // If Player 1 wins in the current subproblem, // then Player 2 will lose, so return 1. if (ans === 2) { memo.set(n, 1); return 1; } } } // If Player 1 cannot make any move, then Player 2 wins. memo.set(n, 2); return 2;}// Driver codeconst n = 8;const res = solve(n);if (res === 1) console.log("1");else console.log("2"); |
Output
1
Time Complexity: O(logN)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Share your thoughts in the comments
