Thursday, 21 January 2016

Maximizing XOR Hacker Rank Problem Solution.

Given two integers, L and R, find the maximal value of A xor B, where A and B satisfy the following condition:
LABR
Input Format
The input contains two lines; L is present in the first line and R in the second line.
Constraints
1LR103
Output Format
The maximal value as mentioned in the problem statement.
Sample Input
10
15
Sample Output
7
Explanation
The input tells us that L=10 and R=15. All the pairs which comply to above condition are the following:
1010=0
1011=1
1012=6
1013=7
1014=4
1015=5
1111=0
1112=7
1113=6
1114=5
1115=4
1212=0
1213=1
1214=2
1215=3
1313=0
1314=3
1315=2
1414=0
1415=1
1515=0
Here two pairs (10, 13) and (11, 12) have maximum xor value 7, and this is the answer.
Solution;

#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;
/*
    *
    * Prosen Ghosh
    * American International University - Bangladesh (AIUB)
    *
*/
int maxXor(int l, int r) {
    int mx = -99999;
    for(int i = l; i <= r; i++){
        for(int j = i; j <= r; j++){
            if((i^j) > mx)mx = (i^j);
        }
    }
    return mx;
}

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

3 comments:

  1. sir,
    why mx = -99999?
    can you please explain?

    ReplyDelete
  2. if i=l,j=i+1 and i^j,it will start from 10^11.
    then how 10^10?

    ReplyDelete
    Replies
    1. my mistake...i think OJ did't evaluated that test case :P
      now i correct it

      Delete