I was asked this question during an technical interview of a big company. I could get to a basic brute forcing solution but was asked to find a better solution (O(n)) since n was told be within limit of 5,00,000.
Given an integer array of positive numbers (p1,p2,.. pn), the task is to find a minimum cost route from first number to last number. The route cost is defined as the summation of XOR's through the array. Example if route is p1,p4,p6,p10 then the route cost is (p1 xor p4) + (p4 xor p6) + (p6 xor p10). Revisiting any number is allowed. We have to find a minimum cost route from p1 to pn. (n<5,00,000)
I could only give a solution that was a brute force approach but it seemed very naive. The interviewer kept asking for some better solution. I was thinking about some greedy approach but couldn't get to the solution. Can you please help me.
We have the triangle inequality
(a XOR b) <= (a XOR c) + (c XOR b) for all a, b, c >= 0,
which can be proved directly by summing over bit positions or by observing that we can embed XOR as a metric in an L1 space where the ith dimension of the point corresponding to a is 2^i if the corresponding bit in the binary representation of a is 1, and 0 if the corresponding bit is 0.
Accordingly, the best path goes straight from the first element to the last with no intermediate stops.