双向AND等于0的整数对

Question

如果两个整数x和y的按位与的结果等于0，则它们构成一个魔幻对。给定一个整数数组，请为每个数组元素查找是否与其他数组元素形成了魔幻对。

输入项

输入的第一行包含一个整数T，表示测试用例的数量。每个测试用例的第一行都有一个整数N，表示给定数组中元素的数量。第二行包含N个单个以空格分隔的整数a1，a2，...，表示给定数组的元素。

输出量

对于每个测试用例，在一行中打印N个空格分隔的整数。如果ai与给定数组的任何其他元素形成一个魔幻对，则ans'i应该等于1。否则ans'i为0。

约束条件

1 <= N，Ai <= 10 ^ 6

我尝试过蛮力。对于每个元素，我检查此数字的按位与是否为零，或者是否与数组中存在的任何其他元素相同。显然，它的时间复杂度为O（N ^ 2），我的大多数测试用例都超时了

这个问题在这里：https : //www.hackerearth.com/challenges/test/netapp-codenet-2017/algorithm/d2d1f6a92c6740278682e88ed42068a4/

谁能建议我一个更好的方法或算法，使其超过时间限制？

蛮力代码：

int n;
cin >> n;
int a[n];
for (int i = 0; i < n; i++)
    cin >> a[i];
int ans[n];
for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
        if (a[i] & a[j] == 0)
            ans[i] = 1;
for (int i = 0; i < n; i++)
    cout << ans[i] << " ";

Answer 1

一种方法是为所有数字（如Trie）创建一个二叉树。

例如，如果您有数组3 6 2 9 10，则二进制数组看起来像

arr = 11，110，10，1001，1010，树想

                                     root
                                /             \
                               0               1
                                 \           /   \ 
                                  1         0     1
                                 / \       / 
                                0   1     0   
                                 \         \   
                                  1         1  

如果我们迭代二进制数组中的每个元素，则与条件匹配的数字（对于元素中的每个设置位应为0，对于元素中的未设置位应为0或1）。

现在，我们只需要将这些位遍历到树中即可。如果我们能够做到，那么至少存在一个满足条件的数字。

时间复杂度O（N）。原因：-有n个数字。每个数字均为32位二进制长度。创建新节点将使用O（1）。因此，O（32N）=> O（N）。inv_arr的时间相同。

注意：尝试将数字转换为32位二进制数字，因为它将覆盖范围内指定的所有数字。否则会导致问题。这里的6和9构成了一个魔幻对，但是inv_arr中的0110不能被遍历，并且由于无法完成最左边0的遍历，因此将导致不存在任何魔幻对。如果所有数字都用相同长度的二进制表示，则遍历树将给出正确的答案。

码

                                     root
                                /             \
                               0               1
                                 \           /   \ 
                                  1         0     1
                                 / \       / 
                                0   1     0   
                                 \         \   
                                  1         1