Find pair of integers such that their sum is twice their Bitwise XOR

Given a positive integer N, the task is to find all pairs of integers (i, j) from the range [1, N] in increasing order of i such that:

• 1 ≤ i, j ≤ N
• i + j = N
• i + j = 2*(i ^ j)
• If there are no such pairs, return a pair {-1, -1}.

Note: Here ‘^’ denotes the bitwise XOR operation.

Examples:

Input: N = 4
Output: {{1, 3}, {3, 1}}
Explanation: A total of 3 pairs satisfy the first condition: (1, 3), (2, 2), (3, 1).
There are only two valid pairs out of them: (1, 3) and (3, 1) as 1 + 3 = 4 = 2 * (1 ^ 3).

Input: 7
Output: {-1, -1}

Input: 144
Output: {{36, 108},  {44, 100}, {100, 44},  {108, 36 }}

Approach: 

The problem can be viewed as a bitwise manipulation problem satisfying pre-conditions. 

If the pairs add upto N then it is obvious that the second element j of the pair can be generated using the first element i as j = N – i. Then we just have to check for the remaining condition  i + j = 2 * (i ^ j).

Follow the steps mentioned below to solve the problem:

• Traverse from 1 to N for first element i and second element as j = N – i.
• Check for N = i + j and N = 2 * (i ^ j) and push the first elements i and j into the 2-D vector ans and increment count.
• Return {-1,  -1} if count = 0 or ans, if count > 0.

Below is the implementation of the above approach.

36 108 
44 100 
100 44 
108 36 

Time Complexity: O(N)
Auxiliary Space: O(1)