1

I was trying this problem on bits manipulation came through this one:

Beauty of a number is the number of set bits in that number. A and B start playing a game where there is number N written on the board,the player whose turn is to move goes to the board and writes a new number N-K where k<=N and beauty of K is 1.It is also important that beauty of N-K must be equal to beauty of N. Last player to successfully complete his move wins the game.

They both play the game optimally.

P.S. i am not looking for a code here.I want to know how to approach this?

RKTSP
  • 99
  • 1
  • 8
  • Game search tree http://en.wikipedia.org/wiki/Game_tree and binary permutations http://en.wikipedia.org/wiki/Permutation – IdeaHat Oct 01 '13 at 14:27
  • Can you provide the link to the problem. I am interested to solve this one if it was on a programming site. Thank you. – Aman Deep Gautam Oct 02 '13 at 08:08
  • no this problem was not on any programming site.actually this is an interview question – RKTSP Oct 02 '13 at 10:57

1 Answers1

1

It is a typical game theory problem. Players play optimally means that any player will make the move such that it maximizes it chance of winning (taking into account that when player 2 gets a chance he will also be willing to do the same).

Now in this case let us see what are the moves allowed:

As required the beauty of a number should remain same and the k should have beauty 1 i.e. only 1 bit set(for ex. 00000100)

For further illustration let us assume that we only have 8 bit number.

If you see closely, for beauty of N to remain same, the bit set in k is at the (one of the) index at which N has a 0 and 1 is at left adjacent to it. I will take an example:

Let us say N is 01010001. now k can be 00100000, 00001000. If you see N-k the beauty remains same. After the operation, you will notice that 1 moves to right and hence 0 moves to left. For example when N=01010001 and k=00100000 (N-k) = 00110001.

Also the ending position of the game will be such that all 0's are to the left and and all 1's are to the right(00000111). You can count the number of moves possible given a number N. If it is odd then the player starting wins otherwise he loses.

Now to count the number of such moves is simple enumeration problem.

Aman Deep Gautam
  • 8,091
  • 21
  • 74
  • 130