Did you know that the minimum XOR pair of an array can be found by sorting the array, then checking the XOR of adjacent elements.

Can anyone prove why?

Before contest

Codeforces Round sponsored by NEAR (Div. 1 + Div. 2)

3 days

Register now »

Codeforces Round sponsored by NEAR (Div. 1 + Div. 2)

3 days

Register now »

*has extra registration

# | User | Rating |
---|---|---|

1 | tourist | 3803 |

2 | jiangly | 3707 |

3 | Benq | 3627 |

4 | ecnerwala | 3584 |

5 | orzdevinwang | 3573 |

6 | Geothermal | 3569 |

6 | cnnfls_csy | 3569 |

8 | Radewoosh | 3542 |

9 | jqdai0815 | 3532 |

10 | gyh20 | 3447 |

# | User | Contrib. |
---|---|---|

1 | awoo | 163 |

2 | maomao90 | 160 |

3 | adamant | 157 |

4 | maroonrk | 155 |

5 | -is-this-fft- | 150 |

6 | Petr | 148 |

6 | SecondThread | 148 |

8 | atcoder_official | 147 |

9 | TheScrasse | 145 |

9 | nor | 145 |

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jul/16/2024 01:54:06 (l2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

That is because the difference in the set bits in the adjacent elements in the sorted array is the minimum. For Example: elements may be 1000, 1001 or 1010 in binary form.

If you consider adjacent elements like 0111 and 1000(again binary form), obviously they won't contribute anything to the minimum, but most likely the element next to 1000 ahead of it in the sorted array will differ in less number of set bits, which may contribute to the minimum. The same analogy goes for elements behind 0111 in the sorted array.

In this way, we can get the minimum xor of any pair, which would obviously have least difference in number of set bits.

Consider a greedy algorithm on a 0-1 Trie.

example 1 example 2

this might help

Let's look at all possible pairs of elements in the array. The minimum XOR is achieved in one of those pairs where the length of the common prefix in the bit representation is the longest. This is because it corresponds to the maximum prefix of zeros at the beginning of the XOR. Hence, the minimum XOR is achieved in one of such pairs. Now, notice that for any such pair, it is true that its elements are consecutive in the sorted array because the elements have the form $$$prefix0 \dots$$$ and $$$prefix1 \dots$$$ If there were at least one more element $$$a_i$$$ between them, the common prefix of $$$a_i$$$ with one of the elements of the pair would be greater than the prefix of the pair. $$$(a_i = prefix0\dots\ or\ prefix1\dots)$$$ But we initially considered pairs with the longest matching bit prefix. Contradiction!

does anyone has list of problems like this where you can learn new XOR properties , such as state above.

https://atcoder.jp/contests/abc308/tasks/abc308_g

you can go through the editorial of this problem

I've understood it from the above comments now. Cheers

Similar approach can be applied to find a maximal AND pair.