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
- Place the input in an array A[1..n]
- Compute the value M(A). This gives the location of the min XOR value (i, (i + 1) % n)
- 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.
- 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
- Given input A[1..n], For i = 1..n and j = (i+1)..n compute x_ij = A[i] XOR A[j]
- Compute the max(x_ij). Note that 2^p <= max(x_ij) < 2^(p+1) for some p.
- 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.
- 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?
A = [2, 2, 4, 4, 2, 2, 4, 4]
, no single swap changesM(A) = 0
, but of course withB = [2, 4, 2, 4, 2, 4, 2, 4]
you haveM(B) = 6
andB
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.