top button
Flag Notify
    Connect to us
      Site Registration

Site Registration

How to find MAX-XOR in an array?

+5 votes
2,379 views

Given an array A of unsigned 32-bit ints, choose two in-bounds indices i, j so as to maximize the value of A[i] ^ A[j], where ^ is the bitwise XOR (exclusive OR) operator. If there are multiple possible answers, print any one.

Example Input:

4 2 0 13 49 

Output:

3 4 

Explanation: 13 ^ 49 is 60, 13 and 49 are positioned at indexes 3 and 4. Printing "4 3" would have been equally valid.
EDIT:- Let k be the bit width (maximum number of bits) of the primitive.
Constraint:- Only Sub-quadratic complexity. An O(k*arr.length) time.

posted Dec 16, 2013 by Atiqur Rahman

Share this question
Facebook Share Button Twitter Share Button LinkedIn Share Button

1 Answer

+1 vote

I am not providing the code (sorry) just the concept -

  1. XOR flips the bits so at some place you should have two numbers which has different bit value at same position.
  2. Find the highest bit and divide the array into two parts such that
    a. one group has all numbers with highest bit set (one number will come from this grp)
    b. other group has all the same bit as reset. (another number will come from this grp)
  3. Not we need to from the highest bit to second highest bit such that
    a. Pick from first group and divide into two parts where second highest bit is set or reset.
    b. Pick from second group and divide into two parts where second highest bit is set or reset.
    in this step you will eliminate lot of numbers where highest bit is different and second highest bit is same.

And run this algo recursively (implementation is not easy) but should give you some pointer.

answer Dec 16, 2013 by Satish Mishra
Similar Questions
+5 votes

Given an unsorted array, find the max length of subsequence in which the numbers are in incremental order.

For example: If the input array is {7, 2, 3, 1, 5, 8, 9, 6}, a subsequence with the most numbers in incremental order is {2, 3, 5, 8, 9} and the expected output is 5.

+8 votes

Given an array of numbers find all such triplets that satisfy the given condition.

Condition: a[i] < a[j] < a[k] where I < j < k.
Is it possible to do in linear time O(N) ?? if yes how??
if not so what would be optimized approach.

+3 votes

In an "N" element integer sorted array, a particular elements is repeating "(N/2)+1" times. How much time it take to find the repeating element.

0 votes

Problem: You have given a stock prices for next 10 days. Find out: max benefit in best time complexity in buy and sell 1 share ?
Condition: Share must be sold any day after buying date.

For ex:
Share price in thousands
5 1 4 6 7 8 4 3 7 9
Max benefit 9 – 1 = 8 thousand

...