Interesting XOR! (IRSTXOR) Solution — Codechef March Long Challenge

Problem Statement

You are given an integer C. Let d be the smallest integer such that 2 power d, is strictly greater than C.

Consider all pairs of non-negative integers (A,B) such that A,B<2 power d, and A⊕B=C (⊕ denotes the bitwise XOR operation). Find the maximum value of A⋅B over all these pairs.


  • The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.


For each test case, print a single line containing one integer ― the maximum possible product A⋅B.


  • 1≤T≤10⁵


Subtask #1 (30 points): 1≤C≤10³

Subtask #2 (70 points): original constraints

Example Input


Example Output



Example case 1: The binary representation of 13 is “1101”. We can use A=10 (“1010” in binary) and B=7 (“0111” in binary). This gives us the product 70. No other valid pair (A,B) can give us a larger product.

Example case 2: The binary representation of 10 is “1010”. We can use A=13 (“1101”) and B=7 (“0111”). This gives us the maximum product 91.

Code (Solution)

The code has been implemented in Java

/* package codechef; // don't place package name! */import java.util.*;import java.lang.*;import*;/* Name of the class has to be "Main" only if the class is public. */class Codechef{public static void main (String[] args) throws java.lang.Exception{Scanner sc = new Scanner(;int t = sc.nextInt();while(t-- > 0){long c =0;c = sc.nextLong();long temp =c;long i=0;while(temp > 0){temp = temp/2;i++;}long a = (int)Math.pow(2,i-1)-1;long b = a^c;System.out.println(a*b);}}}

Hope you would have liked the article. Please give 50 claps to this article and follow me for more future programming related blogs.


Software Developer ,currently pursuing B.Tech in Information Technology. Electronic Dance Music is love.Also like all phone related technologies