CareerCup

The total number of rounds would be number of 0s before each 1 bit set in n. If n = 12 (1100). Then the player-1 selects k=1 to conserve the same number of 1s in the number. So, now n becomes 10(1010). Then player-2 selects k=0 and n becomes 9(1001). Then it continues to 5(0101)->3(0011). Total number of rounds is 4 which is number of zeroes before each 1 bit set in n. If you further look to conserve the property of equal number of 1s the player will select a k such that it is the first zero that has next higher bit set to 1. Here is the code in action:

public int selectWinner (int n) {

	int total = 0;
	int numZeros = 0;

	while (n!=0) {
		if (n&0x01) {
			total +=numZeros;
		} else {
			numZeros++;
		}
		n=n>>1;
}
return (total%2)?2:1;
}

For the input n, in binary format "100101", the first player, A will lose the game, and the second player B, will win. BC, A can change n to "100011" or "10101", at the first round. For "100011", B can easily win the game. For "10101", B can win the game by change it to "10011".
We can change the model of this problem to the following. Considering there are several buckets, in each of them, there are some balls (means the number of '0'), or, nothing. For instance, "100101" can be represented by 2 buckets, the first bucket has 2 balls and second has 1. Then, for each player, he can pick one bucket and move one ball from the this bucket (ith one) to the (i - 1)th bucket. Of cause, we can only move the ball forward. The guy that moves the last ball win the game.

As oldtimer said, the game ends when all ones are on the least significant bits.
So we basically need to count how many swaps we need to make the zeros go to the most significant bits.
For each bit set to 1, the number of swaps needed is equal to the number of 0s in the least significant bits.
If the total number of swaps is odd, player A wins, else B wins.

void Solve(int n) {
    int i, zeros = 0, sum = 0;
    for (i = 0; (i << 1) <= n; i++)
        if ( n & (i << 1) ) // bit set to 1
            sum += zeros;
        else
            zeros++;
    if (sum & 1)
        puts("Player A wins");
    else
        puts("Player B wins");
}

what if n= 11 written on board.....
the binary representation will be [1111]
now second there can be no value of K for which you can get more then 4 one's for eq:
n-2^k

If the last move made by a player was such that allones in binary representation are moved to the lsb position then that player becomes the winner.

eg.
A : 10 [1010]
B : 9 [1001] -> diff.from previous = 2^0
A : 5 [0101] -> diff.from previous = 2^2
B : 3 [0011] -> diff.from previous = 2^1 ==> winner

eg.
A : 13 [1101]
B : 11 [1011] -> diff.from previous = 2^1
A : 7 [0111] -> diff.from previous = 2^2 ==> winner

My answer is,
if you have the value n, and the indexes for n = n[i]*2^i-1 + n[i-1]*2^i-2 + ... + n[2]*2 + n[1]
if you add the indexes a of the values n for which n[a] == 0, and that value is even, then team Friend 1 wins
if you add the indexes and that value is odd then Friend 2 wins

Brute force :

static bool IsWinner(int n)
{
    bool result = false;
    
    for (int i = 0; i < 31 && n > 1 << i; i++)
    {
        if ((n & (1 << i)) == 0 && (n & (1 << (i + 1))) != 0) // detect this one "10"
            result |= !IsWinner(n - (1 << i));
    }
    
    return result;
}

The best solution :

static bool IsWinner2(int n)
{
    int sum = 0;
    int zeros = 0;
    while (n > 0)
    {
        if ((n & 1) != 0) sum += zeros;
        else zeros++;
        
        n >>= 1;
    }
    
    return (sum & 1) != 0 ? true : false; // true - first player win, false - second player win
}

void judgeWinner(int n){
	String b = Integer.toBinaryString(n);
	int extra = 0;
	for(int i = 1; i<b.length(); i++){
		if(b.charAt(i) == '1')
			extra ++;
	}
	int residual = (b.length()-1+ extra)%2;
	if(residual == 0)
		System.out.println("Player 2 wins");
	else
		System.out.println("Player 1 wins");
}

Based on the previous discussion, we can change the question to judge the number of moves to compact the number so at last all the number 1 get stay together, like '11111'. So in order to calculate the total number of moves, we can go through the following ways. First, find the first occurrence of 0 in the sequence. Then find the number 1 just behind this first 0. Then the moves for this round should be the subtract of both first 0 and 1 after it. Then we swap these two numbers in the array.
We keep on the process until we cannot find number 1 after the so called first 0. Then the total number of moves will be the judge base. Let it as count. If count is odd, then that means player 1 wins. Otherwise player 2 wins. The code are attached below, I just print the total move number:

public class WinnerCount {
    public static int firstZeroPosition(int[] array) {
        for(int i = 0; i < array.length; i++) {
            if(array[i] == 0)
                return i;
        }

        return -1;
    }

    public static int firstOneAfterZero(int[] array) {
        int firstZero = firstZeroPosition(array);
        if(firstZero >= 0) {
            for(int i = firstZero + 1; i < array.length; i++)
                if(array[i] > 0)
                    return i;
        }

        return -1;
    }

    public static int count(int[] array) {
        int count = 0;
        int firstIndex = firstOneAfterZero(array);
        while(firstIndex > 0) {
            int firstZero = firstZeroPosition(array);
            count += firstIndex - firstZero;
            swap(array, firstZero, firstIndex);
            firstIndex = firstOneAfterZero(array);
        }

        return count;
    }

    public static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    public static void main(String[] args) {
        int[] a = {0, 1, 0, 1, 0, 1};
        System.out.println(count(a));
    }
}

f(1) = false;
f(n) = !f(n-2^0) | !!f(n-2^1) ... !f(n-2^k) (2^k < n)

bool win(int n){
		if (n == 1)
			return false;
		for(int i=0; i<n; i++)
		{
			int m = pow(2, i);
			if (m >=n){
				break;
			}
			// if (!samebeauty(n, m)) continue;
			if (!win(n-m)){
				return true;
			}
		}
		return false;
	}

is this for phone interview or on site?

Isn't the question to come up with a number that has same number of 1's as the given number before they all run out? If yes, it would be n!/a!(n-a)! where n is the number of all binary digits the max number (10^9) can have, and a is the number of 1's in the given number x. If the result is even one wins otherwise...

assume binary representation of n is of the form

ak ones b(k-1) zeros .... a3 ones b2 zeros a2 ones b1 zeros a1 ones

where ai>0 and bj > 0 (if no zeros at all P2 win)

#swaps to more all ones to least significant positions while staying beautiful would be
s = a2*b1 + a3*(b1+b2) + ... ak*(b1+b2+...b(k-1))


if(s is even) P2 win
else P1 win

If ((total number of bits in n (whether zero or one) - # of one bits in n) & 1) A wins else B wins

If the number of 1s in n is odd, A wins else B wins.