Количество совместимых чисел
Количество совместимых чисел
Два целых числа X и Y называются совместимыми, если результат их побитового «И» равен нулю, то есть X AND Y = 0. Например, числа 77 (10011012
) и 50 (1100102
) совместимы, так как 10011012
AND 1100102
= 02
, а числа 3 (112
) и 6 (1102
) несовместимы, так как 112
AND 1102
= 102
.
Вам дан массив целых чисел A1
, A2
,..., An
. Требуется определить для каждого элемента массива, количество совместимых элементов с ним в данном массиве.
Входные данные
В первой строке записано целое число n (1 ≤ n ≤ 105
) - количество элементов в данном массиве. Во второй строке через пробел записаны n целых чисел A1
, A2
, ..., An
(1 ≤ Ai
≤ 4 * 106
) - элементы данного массива. Числа в массиве могут повторяться.
Выходные данные
Выведите n целых чисел через пробел, то есть количество совместимых чисел для каждого i-го элемента массива.
Пояснение
В первом примере элемент A1
совместим с элементом A2
, поэтому ответ: 1 1.
Во втором примере элемент A1
совместим с элементами A2
, A4
, элемент A2
совместим с элементами A1
, A4
, A5
, элемент A3
совместим с элементом A4
, элемент A4
совместим с элементами A1
, A2
, A3
, элемент A5
совместим с элементом A2
, поэтому ответ: 2 3 1 3 1.
2 50 77
1 1
5 1 2 3 4 5
2 3 1 3 1
7 2 7 8 2 6 10 1
2 1 5 2 2 1 5