Bittijono

import java.math.BigInteger;
import java.util.Scanner;
 
public class Bittijono {
 
    private static BigInteger[] powerOf2 = new BigInteger[61];
 
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
 
        int n = Integer.parseInt(scanner.nextLine());
 
        powerOf2[0] = BigInteger.valueOf(1);
        powerOf2[1] = BigInteger.valueOf(2);
 
        for (int i = 2; i < powerOf2.length; i++) {
            powerOf2[i] = powerOf2[i - 1].multiply(powerOf2[1]);
        }
 
        while (n-- > 0) {
            BigInteger k = new BigInteger(scanner.nextLine());
 
            int power = upperPowerOf2(k);
            BigInteger maxIndex = powerOf2[power];
 
            boolean guess = true;
 
            while (!k.equals(BigInteger.ONE)) {
                BigInteger halfMaxIndex = maxIndex.divide(powerOf2[1]);
                if (k.compareTo(halfMaxIndex) > 0) {
                    guess = !guess;
                    k = k.subtract(maxIndex.divide(powerOf2[1]));
                }
                maxIndex = halfMaxIndex;
            }
 
            if (guess) {
                System.out.println(0);
            } else {
                System.out.println(1);
            }
 
        }
    }
 
    private static int upperPowerOf2(BigInteger num) {
        int low = 0;
        int high = powerOf2.length - 1;
 
        while (true) {
            int middle = (low + high) / 2;
 
            if (powerOf2[low].compareTo(num) >= 0) {
                return low;
            }
 
            if (powerOf2[middle].compareTo(num) == 0) {
                return middle;
            }
 
            if (powerOf2[middle].compareTo(num) < 0) {
                if (middle + 1 <= high && powerOf2[middle + 1].compareTo(num) >= 0) {
                    return middle + 1;
                } else {
                    low = middle + 1;
                }
            } else if (middle - 1 >= low && powerOf2[middle - 1].compareTo(num) < 0) {
                return middle;
            } else {
                high = middle - 1;
            }
        }
    }
 
}

Test 1

Group: 1

Verdict: ACCEPTED

Test 2

Group: 2

Verdict: ACCEPTED

Test 3

Group: 3

Verdict: TIME LIMIT EXCEEDED