Discover winner of the sport when any set bit is eliminated in every transfer

[ad_1]

View Dialogue

Enhance Article

Save Article

Like Article

View Dialogue

Enhance Article

Save Article

Like Article

Two gamers, Participant 1 and Participant 2, are given an integer N to play a recreation. The principles of the sport are as follows : 

  • In a single flip, a participant can take away any set little bit of N in its binary illustration to make a brand new N. 
  • Participant 1 at all times takes the primary flip. 
  • If a participant can’t make a transfer, he loses.

Examples:

Enter: N = 8
Output: 1
Clarification: N = 8
N = 1000 (binary)
Participant 1 takes the bit.
The remaining bits are all zero.
Participant 2 can’t make a transfer,  
so Participant 1 wins.

Enter: N = 3
Output: 2

Method: The given drawback may be solved by following the beneath thought:

Calculate the variety of set bits in N. If the variety of set bits is odd then participant 1 will at all times win [because he will take the following turns – 1st, 3rd, 5th, . . . and any odd turn]. In any other case, participant 2 will win the sport.

Comply with the steps talked about beneath to implement the:

  • Calculate the variety of set bits in N.
  • If the variety of the set bits is odd then participant 1 wins.
  • Else, participant 2 wins.

Under is the implementation of the above strategy.

C++

  

#embrace <bits/stdc++.h>

utilizing namespace std;

  

int swapBitGame(lengthy lengthy N)

{

    int bitCount = 0;

  

    

    

    whereas (N) {

        N = (N & (N - 1));

        bitCount++;

    }

  

    

    

    return bitCount % 2 == 0 ? 2 : 1;

}

  

int major()

{

    lengthy lengthy N = 8;

  

    

    cout << swapBitGame(N) << endl;

  

    return 0;

}

Time Complexity: O(log N)
Auxiliary Area: O(1)

[ad_2]

Leave a Reply

Your email address will not be published. Required fields are marked *