You are viewing a single comment's thread. Return to all comments →
import java.util.Scanner; public class Solution { public static void main(String [] args) { Scanner scan = new Scanner(System.in); int L = scan.nextInt(); int R = scan.nextInt(); scan.close(); int xored = L ^ R; int significantBit = 31 - Integer.numberOfLeadingZeros(xored); int result = (1 << (significantBit + 1)) - 1; System.out.println(result); } }
To maximize A xor B, we want A and B to differ as much as possible at every bit index.
We first find the most significant bit that we can force to differ by looking at L and R.
For all of the lesser significant bits in A and B, we can always ensure that they differ and still have L <= A <= B <= R.
Our final answer will be the number represented by all 1s starting from the most significant bit that differs between A and B
L = 10111 R = 11100 _X___ <-- that's most significant differing bit 01111 <-- here's our final answer
Notice how we don't directly calculate the values of A and B.
From my HackerRank solutions.
Maximizing XOR
You are viewing a single comment's thread. Return to all comments →
Java solution - more efficient than Editorial solution
To maximize A xor B, we want A and B to differ as much as possible at every bit index.
We first find the most significant bit that we can force to differ by looking at L and R.
For all of the lesser significant bits in A and B, we can always ensure that they differ and still have L <= A <= B <= R.
Our final answer will be the number represented by all 1s starting from the most significant bit that differs between A and B
Let's try an example
Notice how we don't directly calculate the values of A and B.
From my HackerRank solutions.