Krdytkyu

I have been working on this hackerrank problem:

Louise and Richard have developed a numbers game. They pick a number (1 ≤ n < 2⁶⁴)
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";

}

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 1s (even number) but you don't remove the last 1 bit so ignore it and say there are 3 1s 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";

}