Interesting XOR! - CodeChef Solution in Java | AskTheCode

CodeChef March Long Challenge Solution| Interesting XOR! solution in Java | AskTheCode

---

Problem:

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

Consider all pairs of non-negative integers (A,B) such that A,B<2d 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.

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:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
import java.lang.*;

class Maths {
    static int power(int x, int y, int p) {
        int res = 1;
        x = x % p;
        if (x == 0)
            return 0;
        while (y > 0) {
            if ((y & 1) != 0)
                res = (res * x) % p;
            y = y >> 1;
            x = (x * x) % p;
        }
        return res;
    }

    static double lg(int n) {
        return Math.log(n) / Math.log(2);
    }

    static double log(int n) {
        return Math.log(n) / Math.log(10);
    }

    static double ln(int n) {
        return Math.log(n);
    }
}

class FastReader {
    BufferedReader br;
    StringTokenizer st;

    public FastReader() {
        br = new BufferedReader(new InputStreamReader(System.in));
    }

    String next() {
        while (st == null || !st.hasMoreElements()) {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
        return st.nextToken();
    }

    int nextInt() {
        return Integer.parseInt(next());
    }

    long nextLong() {
        return Long.parseLong(next());
    }

    double nextDouble() {
        return Double.parseDouble(next());
    }

    String nextLine() {
        String str = "";
        try {
            str = br.readLine();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return str;
    }

    void print(Object... o) {
        for (Object object : o) {
            System.out.print(object + " ");
        }
        System.out.println();
    }

    void arrInt(int arr[], int n) {
        for (int i = 0; i < n; i++) {
            arr[i] = this.nextInt();
        }
    }

    void arrLong(long arr[], int n) {
        for (int i = 0; i < n; i++) {
            arr[i] = this.nextLong();
        }
    }
}
class InterestingXor {
    public static void main(String[] args) {
        FastReader sc = new FastReader();
        int test = sc.nextInt();
        int arr[] = new int[] { 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536,
                131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728,
                268435456, 536870912, 1073741824 };
        while (test-- > 0) {
            int n = sc.nextInt();
            long a=arr[(int) Maths.lg(n)]-1;
            long b=a^n;
            sc.print(a*b);
        }
    }
}