Дисбаланс залежить лише від найбільшого й найменшого елементів обраної підпослідовності. Тому відсортуємо масив — це нічого не змінює, бо порядок елементів у підпослідовності неважливий.
Після сортування можна вважати, що оптимальна підпослідовність — це суцільний відрізок відсортованого масиву. Справді, якщо в підпослідовності є елементи a_l і a_r як крайні, то додавання всіх проміжних елементів не змінює дисбаланс, а побітове OR від цього лише «набирає» біти, тобто не зменшується.
Отже, задача звелася до пошуку найкоротшого (за різницею значень) вікна [l, r], у якому від OR усіх елементів не менший за .
Умова монотонна за розширенням вікна: чим більше елементів, тим більше бітів у OR. Тому працює метод двох вказівників. Рухаємо праву межу , додаючи a_r у вікно, і доки умова виконується — зсуваємо ліву межу праворуч, щоразу оновлюючи відповідь значенням a_r - a_l.
Щоб швидко підтримувати OR вікна, не можна просто зберігати одне число: при видаленні елемента біти не «знімаються». Натомість тримайте масив лічильників — для кожного біта скільки чисел у вікні його містять. Тоді — це кількість бітів з ненульовим лічильником, і його легко оновлювати при додаванні та видаленні.
Якщо навіть OR усього масиву має менший за , відповіді немає — виводимо .
Складність — \mathcal{O}(n \log n + n \cdot B), де B \approx 30 — кількість бітів.