Розглянемо -тий біт. Якщо всі числа, які ми візьмемо в набір матимуть цей біт включений, то неможливо буде вибрати три числа з ксором 0, оскільки в ксорі цей біт входитиме тричі. Проте, після того, як ми взяли всі числа з -тим бітом ми можемо взяти до множини ще щось.
Нехай ми хочемо взяти числа в яких старший біт буде або -тий або -тий. Нехай i > j. Тоді ми можемо набрати в множину всі числа з -тим бітом і всі числа з -тим бітом, в яких -тий біт виключений. Можна показати, що це і буде оптимальний спосіб обрати числа. Можна показати, що в оптимальній відповіді j = i - 1.
Відповідно переберемо . Візьмемо всі числа з проміжку [2^{i - 1}, 2^i + 2^{i - 1}), які належать нашій множині.
Складність розв’язку .