3

I am trying to solve this problem: https://www.interviewstreet.com/challenges/dashboard/#problem/4f9a33ec1b8ea

Suppose that A is a list of n numbers ( A1, A2, A3, ... , An) and B ( B1, B2, B3, .. ,Bn ) is a permutation of these numbers. We say B is K-Manipulative if and only if its following value:

M(B) = min( B1 Xor B2, B2 Xor B3, B3 Xor B4, ... , Bn-1 Xor Bn, Bn Xor B1 ) is not less than 2^K. You are given n number A1 to An, You have to find the biggest K such that there exists a permutation B of these numbers which is K-Manipulative.

Input:

In the first line of the input there is an integer N. In the second line of input there are N integers A1 to An N is not more than 100. Ai is non-negative and will fit in 32-bit integer.

Output:

Print an integer to the output being the answer to the test. If there is no such K print -1 to the output.

Sample Input

3 13 3 10

Sample Output

2

Sample Input

4 1 2 3 4

Sample Output

1

Explanation

First Sample test Here the list A is {13, 3, 10}. One possible permutation of A is, B = (10, 3, 13).

For B, min( B1 xor B2, B2 xor B3, B3 xor B1 ) = min( 10 xor 3, 3 xor 13, 13 xor 10 ) = min( 9, 14, 7 ) = 7.

So there exist a permutation B of A such that M(B) is not less than 4 i.e 2^2. However there does not exist any permutation B of A such that M(B) is not less than 8 ie 2^3. So the maximum possible value of K is 2.

==================================================================================

Here are the attempts I have made so far.


Attempt 1: Greedy Algorithm

  1. Place the input in an array A[1..n]
  2. Compute the value M(A). This gives the location of the min XOR value (i, (i + 1) % n)
  3. Check whether swapping A[i] or A[(i + 1) % n] with any other element of the array increases the value of M(A). If such an element exists, make the swap.
  4. Repeat steps 2 & 3 until the value M(A) cannot be improved.

This gives a local maxima for sure, but I am not sure whether this gives the global maxima.


Attempt 2: Checking for the existence of a permutation given neighbor constraints

  1. Given input A[1..n], For i = 1..n and j = (i+1)..n compute x_ij = A[i] XOR A[j]
  2. Compute the max(x_ij). Note that 2^p <= max(x_ij) < 2^(p+1) for some p.
  3. Collect all x_ij such that x_ij >= 2^p. Note that this collection can be treated as a graph G with nodes {1, 2, .. n} and nodes i and j have an undirected edge between them if x_ij >= 2^p.
  4. Check whether the graph G has a cycle which visits each node exactly once. If such a cycle exists, k = p. Otherwise, let p = p - 1, goto step 3.

This gives the correct answer, but note that in step 4 we are essentially checking whether a graph has a hamiltonian cycle which is a very hard problem.


Any hints or suggestions?

3
  • The greedy algorithm as stated doesn't work. Consider A = [2, 2, 4, 4, 2, 2, 4, 4], no single swap changes M(A) = 0, but of course with B = [2, 4, 2, 4, 2, 4, 2, 4] you have M(B) = 6 and B is 2-manipulative. It may work if you change the condition to increasing the minimum of the XORs of the involved items (or rather the minimum of the XORs' highest set bit, pretending that 0 has bit -1 set), but I'm less than convinced. Jun 22, 2012 at 20:15
  • Agreed, I mentioned the greedy algorithm as an attempt at the solution. Thanks for giving an example that shows it doesn't work. Jun 22, 2012 at 21:28
  • B1 Xor B2 < 2^K if and only if B1 and B2 agree on all but the K low order bits, so G has the very special structure of being complete multipartite.
    – rich
    Jun 22, 2012 at 21:38

3 Answers 3

3

It is possible to solve this problem without going deep into graph theory.

Key inference

The property suggested by rich, is the key to solving this problem:

Following up on my comment: B1 Xor B2 < 2^K if and only if B1 and B2 agree on all but the K low order bits

Based on the above property, we only need to find the highest k for which there are at most n/2 occurrences of each unique higher order bits for every A[i].

In other words, amongst the group of values A[i] >> k, iff each of those values is repeated at most n/2 times, there exists a k-manipulative permutation with all the XOR values >= (2^k).

Why n/2

Suppose if you do have more than n/2 occurrences of any of the unique higher order bits, it is NOT possible to obtain a permutation B, with all the cyclic XORs being non-zero, i.e. there will be at least one B[i] XOR B[(i+1) % N] with all the higher order bits becoming zero, hence making M(B) < 2^k

Pseudocode

k = -1
for (bit = (MAX_BITS - 1) to 0) {
    HashMap count
    for (i = 0 to N - 1) {
        higherOrderVal = A[i] >> bit
        if (higherOrderVal exists in count) {
            count[higherOrderVal] += 1
        }
        else {
            count[higherOrderVal] = 1
        }
    }

    isValid = true
    for (element in count) {
        if (element > N/2) {
            isValid = false
            break
        }
    }
    if (isValid) {
        k = bit
        break
    }
}

The time complexity for this solution is O(M * N) where M is the constant factor representing the maximum number of bits used to represent the numbers (32-bits, 64-bits, etc.), and N is the size of the input array A.

1
  • is a little bug in your code: if (element > N/2) need to replace to if (element > N/2-1) to pass all test cases
    – Arsenius
    May 10, 2019 at 6:42
2

Following up on my comment: B1 Xor B2 < 2^K if and only if B1 and B2 agree on all but the K low order bits, so G has the very special structure of being complete multipartite, with partition labels consisting of all but the K low order bits. A complete multipartite graph is Hamiltonian if and only if there is no majority partition. Plug this fact into Attempt 2.

4
  • Can you clarify a little bit more? Note that G may not be the complete graph when p > 0. G may not have (n \choose 2) edges when step 3 of Attempt 2 is first run. Jun 23, 2012 at 2:26
  • Can you explain what would be the partite sets of G? Jun 23, 2012 at 2:38
  • Each number x belongs to partition (x >>> k), where k is the current value of K that we're testing the feasibility of.
    – rich
    Jun 23, 2012 at 12:26
  • Problem 12.6 in these lecture notes math.lsu.edu/~lither/4171spring11/notes.pdf is asking to prove that a complete k-partite graph has a hamiltonian iff there is no majority partition. Given this fact, this problem can now be solved fairly easily. I am surprised that something like this fact was needed to solve this problem. Jun 26, 2012 at 22:49
0

Greedy Approach #priority_queue

firstly insert all pairs xor value and consecutive index i and j ->pq.push(tuple(v[i]^v[j],i,j)) now pop the first maxm xor value and set the both index i and j now again pop that maxm xor value which is comes from the i or j this operation perform up to 1 to n then return nth poped xor value

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.