Xor profit problem

#1

Hey, I did this problem using two for loops by generating all the possible pairs in O(n^2) time.

Is there any optimization for this problem like O(n) please tell me the optimization for this problem. Any hint or algorithm will be appreciated

#2

Hi,

You can solve this problem in just O(logn) time complexity.

Case1: if(a==b) print 0;
Case2: if(a!=b) then start from most significant bit as there is at least one bit which are different.

#3

When you find the first unequal bit(starting from the most significant bit) ,after that all bits whether same or different you can generate xor as 1 by increasing the bit of x or decreasing the bit of y since they(a and b) will always be between x and y.

#4

Now, try to solve the problem.

#5

I got the approach but suppose how this approach comes to the mind because at first I didn’t got it.
By the thanks for the solution.

#6

Yes, it is difficult to get this approach in mind at one go, but as you solve more and more problems you will get experience of how to attempt questions.

#7

I think i have resolved your doubt. Please mark it resolved if your doubt is cleared.

#8

Sure .
I am marking the doubt as resolved.

#9

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.