# 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.

# Input

- The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
- The first and only line of each test case contains a single integer C.

# Output

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

# Constraints

- 1≤T≤10⁵
- 1≤C≤10⁹

# Subtasks

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

**Subtask #2 (70 points):** original constraints

# Example Input

`2`

13

10

# Example Output

`70`

91

# Explanation

**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 java.io.*;/* 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(System.in);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.

**References**