Finding all pairs of elements (say, a and b) from elements in an array such that a & b is 0.

input: {1, 2, 6, 9, 3}
output: [6,9],[1,2],[2,9],[1,6]

inuput {1, 2, 6, 9, 3, 0}
output: [2,9],[3,0],[2,0],[6,0],[1,6],[9,0],[1,0],[1,2],[6,9]

Solution: Brute force is obivious

 private List<int[]> pairs(int items[]) {
            if (items == null || items.length == 0)
                return Collections.EMPTY_LIST;

            final Set<int[]> pairs = new HashSet<>();

            for (int i = 0; i < items.length; i++) {

                for (int j = i + 1; j < items.length; j++) {

                    int e1 = items[i];
                    int e2 = items[j];

                    if ((e1 & e2) == 0)
                        pairs.add(new int[]{e1, e2});

                }
            }


            return new ArrayList<>(pairs);
        }

Solution 2: I thought about one more solution but that also end up to O(n^2)
Algo:

1. Find all elements whose 1's bit (right most) is set
2. Find all elements whose 1's bit (right most) is NOT set
   Iterate both list and do & and check
   Example: {1, 2, 6, 9, 3}
   1st bit set -> {1,9,3}
   1st bit not set -> {2,6}
   output: [6,9],[1,2],[2,9],[1,6]
   3 will be discard with all of them as 3 & 2!=0 , 3&6!=0

In worst case, the array will be divied in two parts. Hence O(n^2)