TopCoder SRM 723 TopXorer DIV I

Problem Statement: https://community.topcoder.com/stat?c=problem_statement&pm=14736&rd=17027

Description: Given an array of number a, we have find what is the maximum XOR possible among them.One has to choose any number from 0 to a[i]

My Approach: First lets sort the input array. Set the result as maximum of number of  bits required to stored largest a[i]. For example if a =9 which is (1001) i.e. 4 bits set the results as (1111) i.e. 15.

flipped : This array stores whether the first bit of the number is flipped or not. This useful, let me explain with example suppose number is 1001 , to get a smaller number than this , we can flip 0 any any intermediate position only if top most bit is flipped. i.e. 0110 , which is 6 < 9 ,
At the same time if intermediate bit is 1, it can be flipped unconditionally. for example 110 , second bit can be changed to 0 to achieve a smaller number i.e. 5 (101)


Now scan each bit position for every a[i]  For all i =1 to n ( nested loop), note that we skipped largest number.
If number of bit of a[i]  is smaller than current bit position being scanned , skip it.

- Get the value of a[0] at that given position. bit_result
- Next for a[i] get the bit value. my_bit
- if they are different , that means XOR will be 1, we are good , move to next number.
- if they are same ,
    if top bit is flipped or my_bit , then we can flip the bit  , line no 46 & 47
    if we are msb position for that given number and that bit is 1 , flip it
- After we are done scanning every number for that given bit position, we will modify the bit result in result.

Example:
Lets see this with an example

Input: { 129, 0, 1, 257, 1073}

Step 1:  After sorting we get {1073, 257, 129, 1, 0} Now the maximum is 1073 , which can be represented in 11 bit, so set the result as 11 bit number contains all 1's which would be 2047.
This can be achieved by going to next bit position and subtracting 1. i.e. (1< 12 )-1 = 2047.

Steps 2:
Lets represent these number in binary form

	10	9	8	7	6	5	4	3	2	1	0
1073	1	0	0	0	0	1	1	0	0	0	1
257			1	0	0	0	0	0	0	0	1
129				1	0	0	0	0	0	0	1
1											1
0											0

Step 3:

Now for each bit position starting from msb 10 we scan each number.
bit position 10 & 9  will contributes as  is   in result as all other number are smaller
result [10] = 1, result [9] =0
bit position 8:
As the bits are different we will get XOR result as 1 and hence result[8] = 1

bit position 7:

bit_result =0 

for 247, my_bit is 0 and neither the top bit is flipped nor we can flip it either , hence no change.

for 129, my bit is 1 and once again we get result as 1 hence result[7] = 1

bit position:6

bit_result is initialized as 0

for 257, my_bit is 0 and neither the top bit is flipped nor we can flip it either , hence no change.

for 129, my bit is 0 and we cant do much hence result[6] = 0

bit position:5

bit_result is initialized as 1

for 257, my_bit is 0 and its diff that bit_result, so bit_result stays as 1.

for 129, my bit is 0 and its diff that bit_result, so result[5] =1.

 

bit 4 is same as bit 5 and goes result[4] =1

bit 3, 2, 1 are all 0 and result[3] = 0, result[2] = 0, result[1] = 0

bit 0:

bit_result =01

for 247, my_bit is 1 and and it can be flipped

for 129, my bit is 1 and once again it can be flipped.

for 1, my bit is 1 and it can be flipped 

for 0 , my_bit is 0 and its diff than bit_result hence result[0] = 1

Hence Final result = 101 1011 0001 = 1457.

#include <bits/stdc++.h>
#include <algorithm>
#define SET_BIT(a, x)   (a |= ((1<<x)))
#define CLEAR_BIT(a, x)   (a &= (~(1<<x)))
#define IS_SET(a, x)   ((a>>x) & 1)
int modifyBit(int n, int p, bool b)
{
    int mask = 1 << p;
    return (n & ~mask) | ((b << p) & mask);
}
using namespace std;
class TopXorer
{
public:
int maximalRating(vector<int> x)
{
int size[x.size()] ; //stores bit size of each number
sort(x.begin(), x.end(), greater<int>());
bool flipped[x.size()] ; // whether the top most bit is flipped from 1 to 0 or not
for (int j=0; j<x.size(); j++) // msb_pos(x) = bit position of msb e.g msb_pos(23) = 10111 = 4 (counting from 0)
{
size[j] = x[j] ? ((int)log2(x[j])) : 1 ; //log2 of 0 is -inf , so set 1 if input is 0.
flipped[j]=0;
}
int result = (1U << (size[0] +1 )) -1 ;// Set the result as max possible
   // e.g. if biggest number is a 5 bit max possible is 11111 i.e. 31 for (int i = size[0] ;i >=0; i--) // scan each bit position , starting from bit_num of x[0]
{
bool bit_result = IS_SET(x[0], i);
for (int j=1; j<x.size(); j++)
{
if(size[j] < i) // if msb_pos(x[j]) < i , just skip
continue;
bool my_bit = IS_SET(x[j], i);
if(my_bit != bit_result) // XOR will be 1 in that case
bit_result =1;
else // both bits are same and XOR will be 0, try to flip the bit if possible
{
if (flipped[j] || my_bit) /*if top bit of this number is flipped to 0, subsequent bits can be flipped */
{   /*e.g 10000 to get a number lower than this msb has to be flipped first and then other*/
bit_result =1;   /*bit position can take 1 value i.e. 01100 < 10000*/
flipped[j] = true;   /*Another case is if the cureent bit is 1 it can be flipped to 0*/
}   /*for example : 110 can be 100 and still it is lesser*/ else if(size[j] == i && my_bit) /*we are at msb of this number, if this msb is 1 it can be flipped to 0*/
{
bit_result =1;
flipped[j] =1;// Now subsequent bit of this number can be flipped
}
}
}
result = modifyBit(result, i, bit_result);
}
return result;
}
};
int main(int argc, char*argv[])
{
TopXorer a;
//vector<int> b ({10, 6}); //15
vector <int> b({2,2,2});
//vector<int> b ({1073, 0, 129, 1, 1, 1, 1, 1, 257,1,1,1,1,1,1});//1457
//vector <int> b ({512, 6326272, 0, 2056, 2056, 2056, 0, 2056, 2560, 2048, 8200, 512, 270344, 2056, 2048, 8, 2056, 2560, 2048, 2056, 2048, 10248, 8, 8, 2056, 8712, 2568, 10248, 10248, 2056, 2560, 0, 2056, 2568, 2056, 2056, 2056, 8, 10760, 0, 3080, 2056, 2056, 2560, 2056, 8, 2056, 2568, 2056, 2568}); //6602751
cout << a.maximalRating(b);
}