Facebook Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Written Test
your moves are
1100->1010->1001->0101->0011
why will this not happen
1100->1010->1001->0111
why will one player play it badly its written it has to be as beautiful as previous
It says "The beauty of a number depends on the number of one's in its binary representation" so 1001->0111 is not a valid move.
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.
CODE:
int willFirstWin(int result[], int len) {
int i = 1;
while (i < len) {
if (result[i] > 0)
break;
i++;
}
if (i == len)
return -1;
for (i = 1; i < len; i++) {
if (result[i] == 0)
continue;
result[i - 1]++;
result[i]--;
if (willFirstWin(result, len))
return 0;
}
return -1;
}
int willFirstWin(int result[], int len) {
int i = 1;
while (i < len) {
if (result[i] > 0)
break;
i++;
}
if (i == len)
return -1;
for (i = 1; i < len; i++) {
if (result[i] == 0)
continue;
result[i - 1]++;
result[i]--;
if (willFirstWin(result, len))
return 0;
result[i - 1]--;
result[i]++;
}
return -1;
}
B can win the game by change it to "10011".
if B change it to 10011 A can then change it to 1111 where B actually loses
@ kkr.ashish, " the number n-2^k has to be as beautiful as n", therefore, A cannot change "10011" to "1111"
B can win the game by change it to "10011".
if B change it to 10011 A can then change it to 1011, which is as beautiful as 10011?
Both players play optimally. Hence if B changes to 10011, then A changes to 00111 and A wins
@keinnnn
@ kkr.ashish, " the number n-2^k has to be as beautiful as n", therefore, A cannot change "10011" to "1111"
1111 has 4 1's
and 10011 has 3 1's
so 1111 is more beautiful than 10011
so holds good
correct me if i am wrong
@Miguel Oliveira
"Both players play optimally. Hence if B changes to 10011, then A changes to 00111 and A wins" How can you change 10011 to 00111 by doing 100111 - 2^k
??
@kkr.ashish:
"the number n-2^k has to be as beautiful as n", which mean, we need to have the same number of 1s is n and n-2^k , which means, we cannot change 10011 to 1111, because they have different number of 1s. Therefore, if B change the number to 10011, the only choice for A for the next step is to change it to 1011, and B will change it to 111. At the end, B won!
What's more, how can you get the conclusion that "so 1111 is more beautiful than 10011"?
ok my bad .. i assumed the number should be atleast as beautiful.. seems the question seemed to be about equal to
for the given question it seems odd as there is not much choice for the players to make wise decisions the moves are very much forced nothing much they can do
as you can see in the test case you mentioned both return to 10011 state
say for 100110011
there will be total 2+ 3*2 moves possible the ordering can be different but it will be 8 moves
100110011 - > 10110011->1110011->1101011->1011011->111011->110111
->101111->111111
so i assume for 1001100110011
the output will be 2+ 2*3+2*5 = 18 moves
so this looks pretty much fixed if the beauty is preserved
100101 - > 2+ 1*2 = 4 moves so A loses
10101 - > 1+ 2*1 =3 B loses
1011101-> 1+ 4*1 = 5 B loses
please correct me if my understanding is wrong but all the moves are forced , players intelligence will not have any impact on the game for equally beautiful, but if its "atleast" then this problem is very interesting indeed
I think there's still one thing to consider. For each round, as to the number of 0s -- N, we have two cases: [1] N = N-1, that's we move 0 in 1th bucket to 0th bucket. [2]N = N, move 0 in ith bucket to (i-1)th bucket, here i>=2. And for each player, he'll try to keep N (remaining number of 0s after his round) to be even, so that he can always take the last round. I think this is what "play optimally" means in the question. So, we have
int finder(ArrayList<Integer> buckets, int player){
if (buckets.size()==1)
return getOpponent(player);
int N = getTotalNumberOfZeros(buckets, 1, buckets.size()-1);
if (buckets.size()==2)
return N%2==0 ? getOpponent(player): player;
if (N%2!=0){
moveZeroWithoutDecrement();
}else{
if (!1thBucketIsEmpty())
moveZeroWithDecrement();
else
moveZeroWithoutDecrement();
}
return finder(buckets, getOpponent(player));
}
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
Why your thinking is restricted to 4 bit? and also the binary representation of 11 is 1011 and not 1111 which is for 15
n ranges from 0 to 10^9 (10 power 9) which is a 32 bit number and the number 4294967295 has 32 1's in it.
n-2^k = 4294967295
so the problem here is to find the number 'k' for a given 'n' written on the board in order to reach 4294967295
lets think and find out...
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
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
}
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));
}
}
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
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:
- Zero2 October 04, 2013