A luthier's workshop is calibrating a rack of n tuning forks, each ringing at a fixed frequency measured in whole hertz. Two forks with frequencies x and y are said to resonate with each other if the absolute difference between their frequencies is no larger than the smaller of the two frequencies, that is |x - y| <= min(x, y). Note that a fork always resonates with itself.
For quality control, the workshop wants to know the strongest possible beat signature achievable: the maximum value of x XOR y (bitwise exclusive-or) over every resonating pair of frequencies drawn from the rack, where the two forks compared may be the same physical fork.
Print a single integer: the maximum XOR value over all resonating pairs of frequencies (including pairing a fork with itself).
Example 1
Input
3 1 2 4
Expected
6
Explanation
Checking every pair: (1,2) has |1-2|=1<=min(1,2)=1 so it resonates, giving XOR 3. (2,4) has |2-4|=2<=min(2,4)=2 so it resonates, giving XOR 6. (1,4) has |1-4|=3, which is greater than min(1,4)=1, so it does not resonate. Self-pairs always give XOR 0. The maximum over all resonating pairs is 6, from (2,4).
Example 2
Input
5 1 2 3 4 5
Expected
7
Explanation
Among the resonating pairs, (3,4) satisfies |3-4|=1<=min(3,4)=3 and gives XOR 7, which turns out to be the largest value achieved by any resonating pair in this rack (other qualifying pairs such as (2,4) give 6, (3,5) gives 6, and (4,5) gives only 1). The answer is 7.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →