HackerRank 'Maximizing Xor' Solution

by Srikant Padala on June 25, 2016, 10:20 am


Explanation


If L and R have a common prefix, then every number between L and R also have the same prefix, and every possible XOR of two such numbers will zero out that prefix. The rest of the bits, after the prefix, take on various values, and the maximum of the XOR of those bits will be any time the two values are complements of each other, which gives an XOR result of all ones. Every possible final result will thus be of the form 2N-1


Maximizing Xor Problem Statement

Video

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <cstdlib>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
using namespace std;
/*
 * Complete the function below.
 */
/*
1010
1011
1100
1101
1110
1111

1010
1111
----
0101
*/
int maxXor(int l, int r) {
    int p = l ^ r, c = 0;
    while(p) {
        c++;
        p >>= 1;
    }
    return pow(2,c) - 1;
}

int main() {
    int res;
    int _l;
    cin >> _l;
    
    int _r;
    cin >> _r;
    
    res = maxXor(_l, _r);
    cout << res;
    
    return 0;
}

Coming Soon.