title: Integer pairs having biwise AND equal to 0
body: <p>Two integers x and y form a magical pair, if the result of their Bitwise And equals 0. 
  Given an array of integers, find for every array element whether it forms a magical pair with some other array element or not.</p>
  
  <p>Input</p>
  
  <p>First line of the input contains a single integer T denoting the number of test cases.
  The first line of each test case has an integer N denoting the number of elements in the given array. 
  The second line contains N single space-separated integers  a1,a2,...an denoting the elements of the given array.</p>
  
  <p>Output</p>
  
  <p>For each test case ,print N space separated integers in a line.
  If ai forms a magical pair with any other element of the given array , then  ans'i should be equal to 1. Otherwise ans'i is 0.</p>
  
  <p>Constraints</p>
  
  <p>1&lt;=N,Ai&lt;=10^6</p>
  
  <p>I tried brute force. For each element I checked if the bitwise AND of this number is zero or not with any other element present in the array. Obviously, it had a time complexity of O(N^2) and most of my test cases timed out</p>
  
  <p>This problem is here: <a href="https://www.hackerearth.com/challenges/test/netapp-codenet-2017/algorithm/d2d1f6a92c6740278682e88ed42068a4/" rel="nofollow noreferrer">https://www.hackerearth.com/challenges/test/netapp-codenet-2017/algorithm/d2d1f6a92c6740278682e88ed42068a4/</a></p>
  
  <p>Can anyone suggest me a better approach or algorithm so it passes the time limit?</p>
  
  <p>Brute force code:</p>
  
  <pre><code>int n;
  cin &gt;&gt; n;
  int a[n];
  for (int i = 0; i &lt; n; i++)
      cin &gt;&gt; a[i];
  int ans[n];
  for (int i = 0; i &lt; n; i++)
      for (int j = 0; j &lt; n; j++)
          if (a[i] &amp; a[j] == 0)
              ans[i] = 1;
  for (int i = 0; i &lt; n; i++)
      cout &lt;&lt; ans[i] &lt;&lt; " ";
  </code></pre>