“Counter Game” Powers of 2 Game
Multi tool use
up vote
2
down vote
favorite
I have been working on this hackerrank problem:
Louise and Richard have developed a numbers game. They pick a number (1 ≤ n < 264)
and check to see if it is a power of 2. If it is, they divide it by 2.
If not, they reduce it by the next lower number which is a power of 2.
Whoever reduces the number to 1 wins the game. Louise always starts.
Given an initial value, determine who wins the game.
As an example, let the initial value n = 132. It's Louise's turn so
she first determines that 132 is not a power of 2. The next lower
power of is 128, so she subtracts that from 132 and passes 4 to
Richard. 4 is a power of 2, so Richard divides it by 2 and passes 2 to
Louise. Likewise, 2 is a power so she divides it by 2 and reaches 1.
She wins the game.
If they initially set counter to 1, Richard wins. Louise cannot make a
move so she loses.
My question is, could somebody verify/help me with the current time complexity of this? And given this time complexity, what are some ways I could reduce it?
I have tried to solve the time complexity, but it is quite confusing for me. What I have so far is: it takes O(log(N)) time to "reach" a given value N, since you are going up by factors of 2. Here I believe the worst case scenario is every number you land on is a power of two, since whenever you have a number that isn't a power of two, subtracting the highest power of two below it will reduce it by more than you would halving it. With that in mind, you have to "reach" a given value n log(M) times, where M is the first value for N.
So we have Log(N) to reach a value N, and you have to do this log(M) times. The part that confuses me is that the value N halves each time. I don't know how to approach the rest of this. Any help with this would be greatly appreciated.
What are some improvements to my code I could make?
static String counterGame(long n) {
int turn = 0;
long current = 2;
long previous = 2;
if (n == 1) return "Louise";
while (true) {
if (current == n) {
n /= 2;
if (n == 1) {
break;
} else {
turn ^= 1;
current = 2;
previous = 2;
}
} else if (current < n) {
previous = current;
current *= 2;
continue;
} else {
n = n - previous;
if (n == 1) {
break;
}
turn ^= 1;
current = 2;
previous = 2;
}
}
return (turn == 1) ? "Richard" : "Louise";
}
java algorithm programming-challenge complexity
New contributor
add a comment |
up vote
2
down vote
favorite
I have been working on this hackerrank problem:
Louise and Richard have developed a numbers game. They pick a number (1 ≤ n < 264)
and check to see if it is a power of 2. If it is, they divide it by 2.
If not, they reduce it by the next lower number which is a power of 2.
Whoever reduces the number to 1 wins the game. Louise always starts.
Given an initial value, determine who wins the game.
As an example, let the initial value n = 132. It's Louise's turn so
she first determines that 132 is not a power of 2. The next lower
power of is 128, so she subtracts that from 132 and passes 4 to
Richard. 4 is a power of 2, so Richard divides it by 2 and passes 2 to
Louise. Likewise, 2 is a power so she divides it by 2 and reaches 1.
She wins the game.
If they initially set counter to 1, Richard wins. Louise cannot make a
move so she loses.
My question is, could somebody verify/help me with the current time complexity of this? And given this time complexity, what are some ways I could reduce it?
I have tried to solve the time complexity, but it is quite confusing for me. What I have so far is: it takes O(log(N)) time to "reach" a given value N, since you are going up by factors of 2. Here I believe the worst case scenario is every number you land on is a power of two, since whenever you have a number that isn't a power of two, subtracting the highest power of two below it will reduce it by more than you would halving it. With that in mind, you have to "reach" a given value n log(M) times, where M is the first value for N.
So we have Log(N) to reach a value N, and you have to do this log(M) times. The part that confuses me is that the value N halves each time. I don't know how to approach the rest of this. Any help with this would be greatly appreciated.
What are some improvements to my code I could make?
static String counterGame(long n) {
int turn = 0;
long current = 2;
long previous = 2;
if (n == 1) return "Louise";
while (true) {
if (current == n) {
n /= 2;
if (n == 1) {
break;
} else {
turn ^= 1;
current = 2;
previous = 2;
}
} else if (current < n) {
previous = current;
current *= 2;
continue;
} else {
n = n - previous;
if (n == 1) {
break;
}
turn ^= 1;
current = 2;
previous = 2;
}
}
return (turn == 1) ? "Richard" : "Louise";
}
java algorithm programming-challenge complexity
New contributor
add a comment |
up vote
2
down vote
favorite
up vote
2
down vote
favorite
I have been working on this hackerrank problem:
Louise and Richard have developed a numbers game. They pick a number (1 ≤ n < 264)
and check to see if it is a power of 2. If it is, they divide it by 2.
If not, they reduce it by the next lower number which is a power of 2.
Whoever reduces the number to 1 wins the game. Louise always starts.
Given an initial value, determine who wins the game.
As an example, let the initial value n = 132. It's Louise's turn so
she first determines that 132 is not a power of 2. The next lower
power of is 128, so she subtracts that from 132 and passes 4 to
Richard. 4 is a power of 2, so Richard divides it by 2 and passes 2 to
Louise. Likewise, 2 is a power so she divides it by 2 and reaches 1.
She wins the game.
If they initially set counter to 1, Richard wins. Louise cannot make a
move so she loses.
My question is, could somebody verify/help me with the current time complexity of this? And given this time complexity, what are some ways I could reduce it?
I have tried to solve the time complexity, but it is quite confusing for me. What I have so far is: it takes O(log(N)) time to "reach" a given value N, since you are going up by factors of 2. Here I believe the worst case scenario is every number you land on is a power of two, since whenever you have a number that isn't a power of two, subtracting the highest power of two below it will reduce it by more than you would halving it. With that in mind, you have to "reach" a given value n log(M) times, where M is the first value for N.
So we have Log(N) to reach a value N, and you have to do this log(M) times. The part that confuses me is that the value N halves each time. I don't know how to approach the rest of this. Any help with this would be greatly appreciated.
What are some improvements to my code I could make?
static String counterGame(long n) {
int turn = 0;
long current = 2;
long previous = 2;
if (n == 1) return "Louise";
while (true) {
if (current == n) {
n /= 2;
if (n == 1) {
break;
} else {
turn ^= 1;
current = 2;
previous = 2;
}
} else if (current < n) {
previous = current;
current *= 2;
continue;
} else {
n = n - previous;
if (n == 1) {
break;
}
turn ^= 1;
current = 2;
previous = 2;
}
}
return (turn == 1) ? "Richard" : "Louise";
}
java algorithm programming-challenge complexity
New contributor
I have been working on this hackerrank problem:
Louise and Richard have developed a numbers game. They pick a number (1 ≤ n < 264)
and check to see if it is a power of 2. If it is, they divide it by 2.
If not, they reduce it by the next lower number which is a power of 2.
Whoever reduces the number to 1 wins the game. Louise always starts.
Given an initial value, determine who wins the game.
As an example, let the initial value n = 132. It's Louise's turn so
she first determines that 132 is not a power of 2. The next lower
power of is 128, so she subtracts that from 132 and passes 4 to
Richard. 4 is a power of 2, so Richard divides it by 2 and passes 2 to
Louise. Likewise, 2 is a power so she divides it by 2 and reaches 1.
She wins the game.
If they initially set counter to 1, Richard wins. Louise cannot make a
move so she loses.
My question is, could somebody verify/help me with the current time complexity of this? And given this time complexity, what are some ways I could reduce it?
I have tried to solve the time complexity, but it is quite confusing for me. What I have so far is: it takes O(log(N)) time to "reach" a given value N, since you are going up by factors of 2. Here I believe the worst case scenario is every number you land on is a power of two, since whenever you have a number that isn't a power of two, subtracting the highest power of two below it will reduce it by more than you would halving it. With that in mind, you have to "reach" a given value n log(M) times, where M is the first value for N.
So we have Log(N) to reach a value N, and you have to do this log(M) times. The part that confuses me is that the value N halves each time. I don't know how to approach the rest of this. Any help with this would be greatly appreciated.
What are some improvements to my code I could make?
static String counterGame(long n) {
int turn = 0;
long current = 2;
long previous = 2;
if (n == 1) return "Louise";
while (true) {
if (current == n) {
n /= 2;
if (n == 1) {
break;
} else {
turn ^= 1;
current = 2;
previous = 2;
}
} else if (current < n) {
previous = current;
current *= 2;
continue;
} else {
n = n - previous;
if (n == 1) {
break;
}
turn ^= 1;
current = 2;
previous = 2;
}
}
return (turn == 1) ? "Richard" : "Louise";
}
java algorithm programming-challenge complexity
java algorithm programming-challenge complexity
New contributor
New contributor
edited yesterday
200_success
127k15148411
127k15148411
New contributor
asked 2 days ago
Benjamin Patch
111
111
New contributor
New contributor
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
up vote
7
down vote
This can actually be solved with a super efficient 1 line of code, but the explanation is long :)
(and there are a few other things I should point out first)
Your code will fail with any input bigger than $2^{62}$ because you never overshoot this number by multiplying by 2 a power of 2 (in your code: current
). This is because a signed long
has only enough bits to represent powers of 2 up to $2^{62}$ (you could have used it as an unsigned variable to have one extra bit, but it still wouldn't be enough to avoid this problem with the biggest numbers that the challenge says are expected input), multiplying it by 2 will cause the left most bit to become 1, which turns it into a big negative number, and multiplying it by 2 again will make it 0 which will then stay 0 no matter how much you multiply it, so your code will enter an infinite loop.
Once you detect that a number is a power of 2 you shouldn't reset previous
and current
to 2 because a power of 2 divided by 2 is still a power of 2, so you know you can divide current
by 2 together with n
.
A thing you could use to your advantage is the way powers of 2 look in binary code:
power | number | binary | even/odd power
2^0 = 1 = 00001 | even
2^1 = 2 = 00010 | odd
2^2 = 4 = 00100 | even
2^3 = 8 = 01000 | odd
2^4 = 16 = 10000 | even
Notice how all bits are 0 except one, the position of this 1 bit tells you if you need an odd or even number of divisions (turns in the game) to reach 1.
long filter = 0b101010101010101010101010101010101010101010101010101010101010101L;
boolean oddPower = (n & filter) == 0;
As soon as you reach a power of 2, this check is enough to tell you who's gonna win. An odd number of turns left means that the player whose turn it is now will win, otherwise the other player will win.
We can go further with looking at the bits and bypass the need to find the next lower power of 2 to divide n
by it if n
is not a power of 2. As you already know, any power of 2 is represented by a single 1 bit and lots of 0 bits. Now let's take a look at a few numbers represented in binary code:
3 = 0011
4 = 0100
5 = 0101
6 = 0110
7 = 0111
8 = 1000
When the number isn't a power of 2, according to the game you need to remove the next lower power of 2. In binary it's gonna look like removing the left most bit (you can look at the numbers above to confirm this). Given our knowledge and solutions so far, we can rewrite the rules of the game to simple binary operations:
if ( number is a power of 2 ) then:
use the check from the previous part of my answer to figure out the winner.
else:
turn the most left 1 bit to 0.
This means the number of turns until we reach a power of 2 and find the answer depends on how many 1-bits are in the number, and knowing if this number is odd or even - combined with the answer to whether the power you reach is odd or even - is all you really need to know to predict the outcome of the game!
Let's test this solution: here's what you see when you track the changes in a number as the game is played, in binary:
1000000110100
0000000110100
0000000010100
0000000000100
0000000000010
0000000000001
There are 4 1
s (even number) but you don't remove the last 1
bit so ignore it and say there are 3 1
s to be removed (odd number) and the first power of 2 you reach is 4 (even) so overall there will be an odd number of turns taken in the whole game, which you can see is true.
Here is the most optimized code I could possibly write to solve this:
static String counterGame(long n){
boolean richardWins = true;
while((n & 1) == 0){
richardWins = !richardWins;
n >>>= 1;
}
while(n != 1){
if((n & 1) == 1)
richardWins = !richardWins;
n >>>= 1;
}
return richardWins ? "Richard" : "Louise";
}
This code looks at each bit once, so the time complexity of this code is O(log(N))
where N
is the input number, and log(N)
is the worst case scenario for the number of bits needed to represent the input number in binary.
Judging by the fact that the exception to the rules (where Richard wins when Louise gets the 1 at the start of the game) emerges naturally with this solution if you don't add an if statement at the start to take care of it, I'd say this is what the author of this challenge expected to be the best possible answer.
Bonus
There are processor instructions for counting 1
bits and trailing zeros, so you could actually do the whole thing in one line instead of manually looping through the bits, and using these processor instructions is faster:
static String counterGame(long n){
return ((Long.numberOfTrailingZeros(n) & 1) == 1) ^ ((Long.bitCount(n) & 1) == 1) ? "Richard" : "Louise";
}
EDIT: a shorter code suggested by @JS1:
By subtracting one, it turns all the trailing zeroes into trailing ones, so that they can be counted by bitCount.
static String counterGame(long n){
return ((Long.bitCount(n-1) & 1) == 0) ? "Richard" : "Louise";
}
Wow that's actually really cool. Bit manipulation messes with my head but having someone explain things like that always amazes me. Thanks.
– Benjamin Patch
yesterday
2
How about((Long.bitCount(n-1) & 1) == 1)
? By subtracting one, it turns all the trailing zeroes into trailing ones, so that they can be counted bybitCount
. Btw this is the condition for Louise to win.
– JS1
20 hours ago
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
7
down vote
This can actually be solved with a super efficient 1 line of code, but the explanation is long :)
(and there are a few other things I should point out first)
Your code will fail with any input bigger than $2^{62}$ because you never overshoot this number by multiplying by 2 a power of 2 (in your code: current
). This is because a signed long
has only enough bits to represent powers of 2 up to $2^{62}$ (you could have used it as an unsigned variable to have one extra bit, but it still wouldn't be enough to avoid this problem with the biggest numbers that the challenge says are expected input), multiplying it by 2 will cause the left most bit to become 1, which turns it into a big negative number, and multiplying it by 2 again will make it 0 which will then stay 0 no matter how much you multiply it, so your code will enter an infinite loop.
Once you detect that a number is a power of 2 you shouldn't reset previous
and current
to 2 because a power of 2 divided by 2 is still a power of 2, so you know you can divide current
by 2 together with n
.
A thing you could use to your advantage is the way powers of 2 look in binary code:
power | number | binary | even/odd power
2^0 = 1 = 00001 | even
2^1 = 2 = 00010 | odd
2^2 = 4 = 00100 | even
2^3 = 8 = 01000 | odd
2^4 = 16 = 10000 | even
Notice how all bits are 0 except one, the position of this 1 bit tells you if you need an odd or even number of divisions (turns in the game) to reach 1.
long filter = 0b101010101010101010101010101010101010101010101010101010101010101L;
boolean oddPower = (n & filter) == 0;
As soon as you reach a power of 2, this check is enough to tell you who's gonna win. An odd number of turns left means that the player whose turn it is now will win, otherwise the other player will win.
We can go further with looking at the bits and bypass the need to find the next lower power of 2 to divide n
by it if n
is not a power of 2. As you already know, any power of 2 is represented by a single 1 bit and lots of 0 bits. Now let's take a look at a few numbers represented in binary code:
3 = 0011
4 = 0100
5 = 0101
6 = 0110
7 = 0111
8 = 1000
When the number isn't a power of 2, according to the game you need to remove the next lower power of 2. In binary it's gonna look like removing the left most bit (you can look at the numbers above to confirm this). Given our knowledge and solutions so far, we can rewrite the rules of the game to simple binary operations:
if ( number is a power of 2 ) then:
use the check from the previous part of my answer to figure out the winner.
else:
turn the most left 1 bit to 0.
This means the number of turns until we reach a power of 2 and find the answer depends on how many 1-bits are in the number, and knowing if this number is odd or even - combined with the answer to whether the power you reach is odd or even - is all you really need to know to predict the outcome of the game!
Let's test this solution: here's what you see when you track the changes in a number as the game is played, in binary:
1000000110100
0000000110100
0000000010100
0000000000100
0000000000010
0000000000001
There are 4 1
s (even number) but you don't remove the last 1
bit so ignore it and say there are 3 1
s to be removed (odd number) and the first power of 2 you reach is 4 (even) so overall there will be an odd number of turns taken in the whole game, which you can see is true.
Here is the most optimized code I could possibly write to solve this:
static String counterGame(long n){
boolean richardWins = true;
while((n & 1) == 0){
richardWins = !richardWins;
n >>>= 1;
}
while(n != 1){
if((n & 1) == 1)
richardWins = !richardWins;
n >>>= 1;
}
return richardWins ? "Richard" : "Louise";
}
This code looks at each bit once, so the time complexity of this code is O(log(N))
where N
is the input number, and log(N)
is the worst case scenario for the number of bits needed to represent the input number in binary.
Judging by the fact that the exception to the rules (where Richard wins when Louise gets the 1 at the start of the game) emerges naturally with this solution if you don't add an if statement at the start to take care of it, I'd say this is what the author of this challenge expected to be the best possible answer.
Bonus
There are processor instructions for counting 1
bits and trailing zeros, so you could actually do the whole thing in one line instead of manually looping through the bits, and using these processor instructions is faster:
static String counterGame(long n){
return ((Long.numberOfTrailingZeros(n) & 1) == 1) ^ ((Long.bitCount(n) & 1) == 1) ? "Richard" : "Louise";
}
EDIT: a shorter code suggested by @JS1:
By subtracting one, it turns all the trailing zeroes into trailing ones, so that they can be counted by bitCount.
static String counterGame(long n){
return ((Long.bitCount(n-1) & 1) == 0) ? "Richard" : "Louise";
}
Wow that's actually really cool. Bit manipulation messes with my head but having someone explain things like that always amazes me. Thanks.
– Benjamin Patch
yesterday
2
How about((Long.bitCount(n-1) & 1) == 1)
? By subtracting one, it turns all the trailing zeroes into trailing ones, so that they can be counted bybitCount
. Btw this is the condition for Louise to win.
– JS1
20 hours ago
add a comment |
up vote
7
down vote
This can actually be solved with a super efficient 1 line of code, but the explanation is long :)
(and there are a few other things I should point out first)
Your code will fail with any input bigger than $2^{62}$ because you never overshoot this number by multiplying by 2 a power of 2 (in your code: current
). This is because a signed long
has only enough bits to represent powers of 2 up to $2^{62}$ (you could have used it as an unsigned variable to have one extra bit, but it still wouldn't be enough to avoid this problem with the biggest numbers that the challenge says are expected input), multiplying it by 2 will cause the left most bit to become 1, which turns it into a big negative number, and multiplying it by 2 again will make it 0 which will then stay 0 no matter how much you multiply it, so your code will enter an infinite loop.
Once you detect that a number is a power of 2 you shouldn't reset previous
and current
to 2 because a power of 2 divided by 2 is still a power of 2, so you know you can divide current
by 2 together with n
.
A thing you could use to your advantage is the way powers of 2 look in binary code:
power | number | binary | even/odd power
2^0 = 1 = 00001 | even
2^1 = 2 = 00010 | odd
2^2 = 4 = 00100 | even
2^3 = 8 = 01000 | odd
2^4 = 16 = 10000 | even
Notice how all bits are 0 except one, the position of this 1 bit tells you if you need an odd or even number of divisions (turns in the game) to reach 1.
long filter = 0b101010101010101010101010101010101010101010101010101010101010101L;
boolean oddPower = (n & filter) == 0;
As soon as you reach a power of 2, this check is enough to tell you who's gonna win. An odd number of turns left means that the player whose turn it is now will win, otherwise the other player will win.
We can go further with looking at the bits and bypass the need to find the next lower power of 2 to divide n
by it if n
is not a power of 2. As you already know, any power of 2 is represented by a single 1 bit and lots of 0 bits. Now let's take a look at a few numbers represented in binary code:
3 = 0011
4 = 0100
5 = 0101
6 = 0110
7 = 0111
8 = 1000
When the number isn't a power of 2, according to the game you need to remove the next lower power of 2. In binary it's gonna look like removing the left most bit (you can look at the numbers above to confirm this). Given our knowledge and solutions so far, we can rewrite the rules of the game to simple binary operations:
if ( number is a power of 2 ) then:
use the check from the previous part of my answer to figure out the winner.
else:
turn the most left 1 bit to 0.
This means the number of turns until we reach a power of 2 and find the answer depends on how many 1-bits are in the number, and knowing if this number is odd or even - combined with the answer to whether the power you reach is odd or even - is all you really need to know to predict the outcome of the game!
Let's test this solution: here's what you see when you track the changes in a number as the game is played, in binary:
1000000110100
0000000110100
0000000010100
0000000000100
0000000000010
0000000000001
There are 4 1
s (even number) but you don't remove the last 1
bit so ignore it and say there are 3 1
s to be removed (odd number) and the first power of 2 you reach is 4 (even) so overall there will be an odd number of turns taken in the whole game, which you can see is true.
Here is the most optimized code I could possibly write to solve this:
static String counterGame(long n){
boolean richardWins = true;
while((n & 1) == 0){
richardWins = !richardWins;
n >>>= 1;
}
while(n != 1){
if((n & 1) == 1)
richardWins = !richardWins;
n >>>= 1;
}
return richardWins ? "Richard" : "Louise";
}
This code looks at each bit once, so the time complexity of this code is O(log(N))
where N
is the input number, and log(N)
is the worst case scenario for the number of bits needed to represent the input number in binary.
Judging by the fact that the exception to the rules (where Richard wins when Louise gets the 1 at the start of the game) emerges naturally with this solution if you don't add an if statement at the start to take care of it, I'd say this is what the author of this challenge expected to be the best possible answer.
Bonus
There are processor instructions for counting 1
bits and trailing zeros, so you could actually do the whole thing in one line instead of manually looping through the bits, and using these processor instructions is faster:
static String counterGame(long n){
return ((Long.numberOfTrailingZeros(n) & 1) == 1) ^ ((Long.bitCount(n) & 1) == 1) ? "Richard" : "Louise";
}
EDIT: a shorter code suggested by @JS1:
By subtracting one, it turns all the trailing zeroes into trailing ones, so that they can be counted by bitCount.
static String counterGame(long n){
return ((Long.bitCount(n-1) & 1) == 0) ? "Richard" : "Louise";
}
Wow that's actually really cool. Bit manipulation messes with my head but having someone explain things like that always amazes me. Thanks.
– Benjamin Patch
yesterday
2
How about((Long.bitCount(n-1) & 1) == 1)
? By subtracting one, it turns all the trailing zeroes into trailing ones, so that they can be counted bybitCount
. Btw this is the condition for Louise to win.
– JS1
20 hours ago
add a comment |
up vote
7
down vote
up vote
7
down vote
This can actually be solved with a super efficient 1 line of code, but the explanation is long :)
(and there are a few other things I should point out first)
Your code will fail with any input bigger than $2^{62}$ because you never overshoot this number by multiplying by 2 a power of 2 (in your code: current
). This is because a signed long
has only enough bits to represent powers of 2 up to $2^{62}$ (you could have used it as an unsigned variable to have one extra bit, but it still wouldn't be enough to avoid this problem with the biggest numbers that the challenge says are expected input), multiplying it by 2 will cause the left most bit to become 1, which turns it into a big negative number, and multiplying it by 2 again will make it 0 which will then stay 0 no matter how much you multiply it, so your code will enter an infinite loop.
Once you detect that a number is a power of 2 you shouldn't reset previous
and current
to 2 because a power of 2 divided by 2 is still a power of 2, so you know you can divide current
by 2 together with n
.
A thing you could use to your advantage is the way powers of 2 look in binary code:
power | number | binary | even/odd power
2^0 = 1 = 00001 | even
2^1 = 2 = 00010 | odd
2^2 = 4 = 00100 | even
2^3 = 8 = 01000 | odd
2^4 = 16 = 10000 | even
Notice how all bits are 0 except one, the position of this 1 bit tells you if you need an odd or even number of divisions (turns in the game) to reach 1.
long filter = 0b101010101010101010101010101010101010101010101010101010101010101L;
boolean oddPower = (n & filter) == 0;
As soon as you reach a power of 2, this check is enough to tell you who's gonna win. An odd number of turns left means that the player whose turn it is now will win, otherwise the other player will win.
We can go further with looking at the bits and bypass the need to find the next lower power of 2 to divide n
by it if n
is not a power of 2. As you already know, any power of 2 is represented by a single 1 bit and lots of 0 bits. Now let's take a look at a few numbers represented in binary code:
3 = 0011
4 = 0100
5 = 0101
6 = 0110
7 = 0111
8 = 1000
When the number isn't a power of 2, according to the game you need to remove the next lower power of 2. In binary it's gonna look like removing the left most bit (you can look at the numbers above to confirm this). Given our knowledge and solutions so far, we can rewrite the rules of the game to simple binary operations:
if ( number is a power of 2 ) then:
use the check from the previous part of my answer to figure out the winner.
else:
turn the most left 1 bit to 0.
This means the number of turns until we reach a power of 2 and find the answer depends on how many 1-bits are in the number, and knowing if this number is odd or even - combined with the answer to whether the power you reach is odd or even - is all you really need to know to predict the outcome of the game!
Let's test this solution: here's what you see when you track the changes in a number as the game is played, in binary:
1000000110100
0000000110100
0000000010100
0000000000100
0000000000010
0000000000001
There are 4 1
s (even number) but you don't remove the last 1
bit so ignore it and say there are 3 1
s to be removed (odd number) and the first power of 2 you reach is 4 (even) so overall there will be an odd number of turns taken in the whole game, which you can see is true.
Here is the most optimized code I could possibly write to solve this:
static String counterGame(long n){
boolean richardWins = true;
while((n & 1) == 0){
richardWins = !richardWins;
n >>>= 1;
}
while(n != 1){
if((n & 1) == 1)
richardWins = !richardWins;
n >>>= 1;
}
return richardWins ? "Richard" : "Louise";
}
This code looks at each bit once, so the time complexity of this code is O(log(N))
where N
is the input number, and log(N)
is the worst case scenario for the number of bits needed to represent the input number in binary.
Judging by the fact that the exception to the rules (where Richard wins when Louise gets the 1 at the start of the game) emerges naturally with this solution if you don't add an if statement at the start to take care of it, I'd say this is what the author of this challenge expected to be the best possible answer.
Bonus
There are processor instructions for counting 1
bits and trailing zeros, so you could actually do the whole thing in one line instead of manually looping through the bits, and using these processor instructions is faster:
static String counterGame(long n){
return ((Long.numberOfTrailingZeros(n) & 1) == 1) ^ ((Long.bitCount(n) & 1) == 1) ? "Richard" : "Louise";
}
EDIT: a shorter code suggested by @JS1:
By subtracting one, it turns all the trailing zeroes into trailing ones, so that they can be counted by bitCount.
static String counterGame(long n){
return ((Long.bitCount(n-1) & 1) == 0) ? "Richard" : "Louise";
}
This can actually be solved with a super efficient 1 line of code, but the explanation is long :)
(and there are a few other things I should point out first)
Your code will fail with any input bigger than $2^{62}$ because you never overshoot this number by multiplying by 2 a power of 2 (in your code: current
). This is because a signed long
has only enough bits to represent powers of 2 up to $2^{62}$ (you could have used it as an unsigned variable to have one extra bit, but it still wouldn't be enough to avoid this problem with the biggest numbers that the challenge says are expected input), multiplying it by 2 will cause the left most bit to become 1, which turns it into a big negative number, and multiplying it by 2 again will make it 0 which will then stay 0 no matter how much you multiply it, so your code will enter an infinite loop.
Once you detect that a number is a power of 2 you shouldn't reset previous
and current
to 2 because a power of 2 divided by 2 is still a power of 2, so you know you can divide current
by 2 together with n
.
A thing you could use to your advantage is the way powers of 2 look in binary code:
power | number | binary | even/odd power
2^0 = 1 = 00001 | even
2^1 = 2 = 00010 | odd
2^2 = 4 = 00100 | even
2^3 = 8 = 01000 | odd
2^4 = 16 = 10000 | even
Notice how all bits are 0 except one, the position of this 1 bit tells you if you need an odd or even number of divisions (turns in the game) to reach 1.
long filter = 0b101010101010101010101010101010101010101010101010101010101010101L;
boolean oddPower = (n & filter) == 0;
As soon as you reach a power of 2, this check is enough to tell you who's gonna win. An odd number of turns left means that the player whose turn it is now will win, otherwise the other player will win.
We can go further with looking at the bits and bypass the need to find the next lower power of 2 to divide n
by it if n
is not a power of 2. As you already know, any power of 2 is represented by a single 1 bit and lots of 0 bits. Now let's take a look at a few numbers represented in binary code:
3 = 0011
4 = 0100
5 = 0101
6 = 0110
7 = 0111
8 = 1000
When the number isn't a power of 2, according to the game you need to remove the next lower power of 2. In binary it's gonna look like removing the left most bit (you can look at the numbers above to confirm this). Given our knowledge and solutions so far, we can rewrite the rules of the game to simple binary operations:
if ( number is a power of 2 ) then:
use the check from the previous part of my answer to figure out the winner.
else:
turn the most left 1 bit to 0.
This means the number of turns until we reach a power of 2 and find the answer depends on how many 1-bits are in the number, and knowing if this number is odd or even - combined with the answer to whether the power you reach is odd or even - is all you really need to know to predict the outcome of the game!
Let's test this solution: here's what you see when you track the changes in a number as the game is played, in binary:
1000000110100
0000000110100
0000000010100
0000000000100
0000000000010
0000000000001
There are 4 1
s (even number) but you don't remove the last 1
bit so ignore it and say there are 3 1
s to be removed (odd number) and the first power of 2 you reach is 4 (even) so overall there will be an odd number of turns taken in the whole game, which you can see is true.
Here is the most optimized code I could possibly write to solve this:
static String counterGame(long n){
boolean richardWins = true;
while((n & 1) == 0){
richardWins = !richardWins;
n >>>= 1;
}
while(n != 1){
if((n & 1) == 1)
richardWins = !richardWins;
n >>>= 1;
}
return richardWins ? "Richard" : "Louise";
}
This code looks at each bit once, so the time complexity of this code is O(log(N))
where N
is the input number, and log(N)
is the worst case scenario for the number of bits needed to represent the input number in binary.
Judging by the fact that the exception to the rules (where Richard wins when Louise gets the 1 at the start of the game) emerges naturally with this solution if you don't add an if statement at the start to take care of it, I'd say this is what the author of this challenge expected to be the best possible answer.
Bonus
There are processor instructions for counting 1
bits and trailing zeros, so you could actually do the whole thing in one line instead of manually looping through the bits, and using these processor instructions is faster:
static String counterGame(long n){
return ((Long.numberOfTrailingZeros(n) & 1) == 1) ^ ((Long.bitCount(n) & 1) == 1) ? "Richard" : "Louise";
}
EDIT: a shorter code suggested by @JS1:
By subtracting one, it turns all the trailing zeroes into trailing ones, so that they can be counted by bitCount.
static String counterGame(long n){
return ((Long.bitCount(n-1) & 1) == 0) ? "Richard" : "Louise";
}
edited 18 hours ago
answered yesterday
potato
1767
1767
Wow that's actually really cool. Bit manipulation messes with my head but having someone explain things like that always amazes me. Thanks.
– Benjamin Patch
yesterday
2
How about((Long.bitCount(n-1) & 1) == 1)
? By subtracting one, it turns all the trailing zeroes into trailing ones, so that they can be counted bybitCount
. Btw this is the condition for Louise to win.
– JS1
20 hours ago
add a comment |
Wow that's actually really cool. Bit manipulation messes with my head but having someone explain things like that always amazes me. Thanks.
– Benjamin Patch
yesterday
2
How about((Long.bitCount(n-1) & 1) == 1)
? By subtracting one, it turns all the trailing zeroes into trailing ones, so that they can be counted bybitCount
. Btw this is the condition for Louise to win.
– JS1
20 hours ago
Wow that's actually really cool. Bit manipulation messes with my head but having someone explain things like that always amazes me. Thanks.
– Benjamin Patch
yesterday
Wow that's actually really cool. Bit manipulation messes with my head but having someone explain things like that always amazes me. Thanks.
– Benjamin Patch
yesterday
2
2
How about
((Long.bitCount(n-1) & 1) == 1)
? By subtracting one, it turns all the trailing zeroes into trailing ones, so that they can be counted by bitCount
. Btw this is the condition for Louise to win.– JS1
20 hours ago
How about
((Long.bitCount(n-1) & 1) == 1)
? By subtracting one, it turns all the trailing zeroes into trailing ones, so that they can be counted by bitCount
. Btw this is the condition for Louise to win.– JS1
20 hours ago
add a comment |
Benjamin Patch is a new contributor. Be nice, and check out our Code of Conduct.
Benjamin Patch is a new contributor. Be nice, and check out our Code of Conduct.
Benjamin Patch is a new contributor. Be nice, and check out our Code of Conduct.
Benjamin Patch is a new contributor. Be nice, and check out our Code of Conduct.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f208414%2fcounter-game-powers-of-2-game%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
RtlQ1z2oQL9i