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.

Output

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

Constraints

  • 1≤T≤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

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