Maximizing XOR
Maximizing XOR
+ 1 comment C++ O(1) solution:
int maximizingXor(int l, int r) { int x = l ^ r, p = 1; while ((x & (p - 1)) != x) p <<= 1; return p - 1; }
Why this works.. this looks for highest bit which is different between l and r: for example (11, 12) that is third bit with value 4.. all bits above it are identical in both l and r, and you can not produce any l<=a<=b<=r which have non zero result of a^b. But you can find value a which has third bit zero and all remaining bits set (11 in this example), and b = a + 1 will clear all lower bits and set third bit, so a^b is all ones from highest difference bit down to bottom bit = maximum xor difference. qed.
+ 0 comments JAVA SOLUTION || Brute+BitManipulation
public static int maximizingXor(int l, int r) { // Write your code here int res=0; int xor=0; int fval=0; for(int i=l;i<=r;i++){ for(int j=i;j<=r;j++){ res=i^j; if(xor fval=xor; } return fval; }
+ 0 comments JavaScript
let max_value = 0; for(let i = l; i <= r; i++) { for(let j = i; j <= r; j++) { const v = i ^ j; if(max_value < v) { max_value = v; } } } return max_value;
+ 0 comments Brute force (java):
public static int maximizingXor(int l, int r) { int max = 0; for(int i = l; i < r; i++) { int xored = i ^ (i + 1); if(xored > max) { max = xored; } } return max; }
+ 0 comments Java : T.C= O(r-l), Using properties of Bitwise operation. All-Correct
public static int maximizingXor(int l, int r) { int max=Integer.MIN_VALUE; int a,b; a=l; for(int i=l;i<r;i++) { b=i+1; if(a!=b) { if((a^b) > max) max=a^b; } // assign a=b b=a^b; a=a^b; } return max; }
}
Sort 456 Discussions, By:
Please Login in order to post a comment