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

https://www.codechef.com/MARCH21C/problems/IRSTXOR