Problem: A Game of 2

One day Karan and Arjun were playing a game. The game always starts with Karan as he is the younger brother among the two and thereafter play alternate turns. They always try to show their power to each other but this time they decided to show it with numbers. Both of them like the number 2. So they decided to play it with 2. First they decide a random numbern and then they take some actions on the number n. If they found that number is not a power of 2, then they reduce the number by the largest power of 2 less than the number and if they found that the number is a power of 2, they simply reduces the number by the half. Then they perform the same operations with the new number generated until the number n becomes 1 and further no one can play the game. The last person to make a valid move will win the game.

Input:
The first line contains an integer T, the number of test cases. Then T test cases follow. Each test case will contain an integer n, denoting the starting number.

Output:
For each test case in a new line print the winner of the game.
Constraints:
1<=T<=30
1<=n<=264-1
Example:
Input:
2
6
2
Output:
Arjun
Karan

Explanation:
For first test case 6 is not a power of 2 Karan takes the largest power of 2 less than 6 which is 4 in this case and reduces the n to 2. Now 2 is a power of 2 therefore Arjun reduces it to half and number becomes 1 and afterwards Karan cannot make a move and therefore lose the game.

Implementation: Python 2.7

import math
def gameOfTwo(number):
    arjun_turn, karan_turn = False, True
    if number == 1:
        return (True, False)
    while number > 1:
        if isPowerOfTwo(number):
            number /= 2
        else:
            number -= getBiggestPowerOfTwoSmaller(number)
        
        if number == 1:
            break
        arjun_turn, karan_turn = karan_turn, arjun_turn
    return (arjun_turn, karan_turn)

def isPowerOfTwo(number):
    return True if 2**int(math.log(number, 2)) == number else False

def getBiggestPowerOfTwoSmaller(number):
    max_pow = -1
    for _ in range(1, 65):
        temp = 2**_
        if temp > max_pow and temp < number:
            max_pow = temp
    return max_pow

if __name__ == '__main__':
    t = input()
    for i in range(t):
        n = input()
        arjun_win, karan_win = gameOfTwo(n)
        print 'Arjun' if arjun_win else 'Karan'
Advertisements