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

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.