Минимальное количество удалений, которые необходимо выполнить в данном массиве, чтобы сумма каждой пары была степенью двойки.

Для заданного массива arr[] , состоящего из N целых чисел, задача состоит в том, чтобы найти минимальное количество элементов, которые необходимо удалить, так что для каждого оставшегося элемента arr[i] существует другой элемент arr[j], (i!=j ) такой, что сумма arr[i] и arr[j] является степенью числа 2 . Если после любого числа удалений такой пары не существует, выведите -1.

Примеры:

Input: arr[] ={1, 2, 3, 4, 5, 6}, N = 6
Output: 1
Explanation: 
Removing 4 is sufficient as, for the remaining elements there exist an element such that their sum is a power of 2:

1. For 1, there exists 3 such that (1+3=4) is a power of 2.
2. For 2, there exists 6 such that (2+6=8) is a power of 2.
3. For 3, there exists 1 such that (3+1=4) is a power of 2.
4. For 5, there exists 3 such that (5+3=8) is a power of 2.
5. For 6, there exists 2 such that (6+2=8) is a power of 2.

Input: A={1, 5, 10, 25, 50}, N=5
Output: -1

Подход: Идея состоит в том, чтобы использовать побитовые операторы и карту для отслеживания частот каждого элемента. Выполните следующие шаги, чтобы решить проблему:

• Инициализируйте переменную равным 0 , чтобы сохранить количество удаляемых элементов.
• Вычислите частоту всех элементов в arr[] и сохраните их на карте, скажем, mp .
• Итерируйте от 0 до N-1 и для каждого текущего индекса i сделайте следующее:
  • Инициализируйте переменную, скажем, flagto 0 .
  • Итерируйте от 0 до 30 и для каждого текущего индекса j сделайте следующее:
    • Если разница между 2 ^j и arr[i] равна arr[i], а частота arr[i] больше 1 , увеличивается флаг и прерывается.
    • В противном случае, если частота разницы между 2 ^j и arr[i] больше 0 , увеличивается флаг и прерывается.
  • Если флаг по-прежнему равен 0 , увеличьте значение an, так как текущий элемент необходимо удалить.
• Наконец, после выполнения вышеуказанных шагов выведите количество удаленных элементов как значение, полученное в ans , если оно меньше, чем равно N. В противном случае выведите -1.

Ниже приведена реализация описанного выше подхода:

Временная сложность: O(30*N)
Вспомогательное пространство: O(1)