What is the difference between this C++ code and this Python code?

Question

Answer

Thanks to @TheDark for spotting the overflow. The new C++ solution is pretty freakin' funny, too. It's extremely redundant:

if(2*i > n && 2*i > i)

replaced the old line of code if(2*i > n).

Background

I'm doing this problem on HackerRank, though the problem may not be entirely related to this question. If you cannot see the webpage, or have to make an account and don't want to, the problem is listed in plain text below.

Question

My C++ code is timing out, but my python code is not. I first suspected this was due to overflow, but I used sizeof to be sure that unsigned long long can reach 2^64 - 1, the upper limit of the problem.

I practically translated my C++ code directly into Python to see if it was my algorithms causing the timeouts, but to my surprise my Python code passed every test case.

C++ code:

#include <iostream>

bool pot(unsigned long long n)
{
    if (n % 2 == 0) return pot(n/2);
    return (n==1); // returns true if n is power of two
}

unsigned long long gpt(unsigned long long n)
{
    unsigned long long i = 1;
    while(2*i < n) {
        i *= 2;
    }
    return i; // returns greatest power of two less than n
}

int main()
{    
    unsigned int t;
    std::cin >> t;
    std::cout << sizeof(unsigned long long) << std::endl;
    for(unsigned int i = 0; i < t; i++)
    {
        unsigned long long n;
        unsigned long long count = 1;
        std::cin >> n;
        while(n > 1) {
            if (pot(n)) n /= 2;
            else n -= gpt(n);
            count++;
        }
        if (count % 2 == 0) std::cout << "Louise" << std::endl;
        else std::cout << "Richard" << std::endl;
    }
}

Python 2.7 code:

def pot(n):
    while n % 2 == 0:
        n/=2
    return n==1

def gpt(n):
    i = 1
    while 2*i < n:
        i *= 2
    return i

t = int(raw_input())
for i in range(t):
    n = int(raw_input())
    count = 1
    while n != 1:
        if pot(n):
            n /= 2
        else:
            n -= gpt(n)
        count += 1
    if count % 2 == 0:
        print "Louise"
    else:
        print "Richard"

To me, both versions look identical. I still think I'm somehow being fooled and am actually getting overflow, causing timeouts, in my C++ code.

Problem

Louise and Richard play a game. They have a counter is set to N. Louise gets the first turn and the turns alternate thereafter. In the game, they perform the following operations.

If N is not a power of 2, they reduce the counter by the largest power of 2 less than N.

If N is a power of 2, they reduce the counter by half of N.

The resultant value is the new N which is again used for subsequent operations.

The game ends when the counter reduces to 1, i.e., N == 1, and the last person to make a valid move wins.

Given N, your task is to find the winner of the game.

Input Format

The first line contains an integer T, the number of testcases. T lines follow. Each line contains N, the initial number set in the counter.

Constraints

1 ≤ T ≤ 10

1 ≤ N ≤ 2^64 - 1

Output Format

For each test case, print the winner's name in a new line. So if Louise wins the game, print "Louise". Otherwise, print "Richard". (Quotes are for clarity)

Sample Input

1

6

Sample Output

Richard

Explanation

As 6 is not a power of 2, Louise reduces the largest power of 2 less than 6 i.e., 4, and hence the counter reduces to 2.

As 2 is a power of 2, Richard reduces the counter by half of 2 i.e., 1. Hence the counter reduces to 1.

As we reach the terminating condition with N == 1, Richard wins the game.

Answer 1

Try this bit-twiddling hack, which is probably slightly faster:

unsigned long largest_power_of_two_not_greater_than(unsigned long x) {
  for (unsigned long y; (y = x & (x - 1)); x = y) {}
  return x;
}

x&(x-1) is x without its least significant one-bit. So y will be zero (terminating the loop) exactly when x has been reduced to a power of two, which will be the largest power of two not greater than the original x. The loop is executed once for every 1-bit in x, which is on average half as many iterations as your approach. Also, this one has not issues with overflow. (It does return 0 if the original x was 0. That may or may not be what you want.)

Note the if the original x was a power of two, that value is simply returned immediately. So the function doubles as a test whether x is a power of two (or 0).

While that is fun and all, in real-life code you'd probably be better off finding your compiler's equivalent to this gcc built-in (unless your compiler is gcc, in which case here it is):

• Built-in Function: int __builtin_clz (unsigned int x) Returns the number of leading 0-bits in X, starting at the most significant bit position. If X is 0, the result is undefined.

(Also available as __builtin_clzl for unsigned long arguments and __builtin_clzll for unsigned long long.)

Answer 2

When n is greater than 2^63, your gpt function will eventually have i as 2^63 and then multiply 2^63 by 2, giving an overflow and a value of 0. This will then end up with an infinite loop, multiplying 0 by 2 each time.