Number of Compatible Numbers#7800
Two integers and are considered compatible if their bitwise "AND" operation results in zero, i.e., AND Y = 0. For instance, the numbers (1001101_2) and (110010_2) are compatible because 1001101_2 AND 110010_2 = 0_2. Conversely, the numbers (11_2) and (110_2) are not compatible since 11_2 AND 110_2 = 10_2.
You are provided with an array of integers A_1, A_2, \ldots, A_n. Your task is to determine, for each element in the array, how many other elements in the array are compatible with it.
The first line contains an integer (1 \le n \le 10^5), representing the number of elements in the array. The second line contains integers A_1, A_2, \ldots, A_n (1 \le A_i \le 4 \cdot 10^6), which are the elements of the array. The numbers in the array may repeat.
Output integers separated by spaces, where each integer represents the number of compatible numbers for the corresponding -th element of the array.
Example 1
Example 2
Example 3
In the first example, element A_1 is compatible with element A_2, so the output is: .
In the second example, element A_1 is compatible with elements A_2, A_4; element A_2 is compatible with elements A_1, A_4, A_5; element A_3 is compatible with element A_4; element A_4 is compatible with elements A_1, A_2, A_3; element A_5 is compatible with element A_2. Therefore, the output is: .