title: XOR greater than 4 of even-even or odd odd pair
body: <p>Given an array of even and odd numbers, I want to get the number of (even-even) and (odd-odd) pairs whose XOR is greater than or equal to 4. I tried this with the code below but it runs in O(n^2), (yikes). Please can anyone suggest a means of optimization?</p>
  
  <pre><code>n = int(raw_input()) #array size
  
  ar = map(int, raw_input().split()) #the array
  
  cnt = 0
  
  for i in xrange(len(ar)):
  
      for j in xrange(i+1, len(ar)):
  
          if ar[i] ^ ar[j] &gt;= 4 and (not ar[i] &amp; 1  and not ar[j] &amp; 1):
  
              cnt += 1; #print ar[i],ar[j],ar[i]^ar[j];
  
          elif ar[i] ^ ar[j] &gt;= 4 and (ar[i] &amp; 1 and ar[j] &amp; 1):
  
              cnt += 1
  print cnt
  </code></pre>
  
  <p>EDIT: I discovered something. any number x, which gives a remainder after % 4, i.e x % 4 != 0, will result to 2 when XORed to a number -2 itself. For example, 6. It is not divisible by 4, therefore, 6 XOR 6-2 (4),==> 2. 10 is not divisible by 4, hence, 10 XOR 10-2 (8) ==> 2. Can you please tell me how this could help me optimize my code? I just know now that I will just look for numbers divisible by 4 and find the count of their + 2.</p>