CODEWITHSUNDEEP
algorithmmath
Shubhashis
Shubhashis

Reputation: 10631

Given an XOR and SUM of two numbers, how to find the number of pairs that satisfy them?

I think the question may be a bit confusing. So, I'll try to explain it first.

Let's say the XOR and SUM of two numbers are given. (Note that there are multiple pairs that may satisfy this.)

For example, If the XOR is 5 and the SUM is 9 there are 4 pairs satisfying the SUM and XOR. They are (2, 7), (3, 6), (6, 3), (7, 2). So 2+7=9 and 2^7=5.

I just want to find the number of pairs that satisfies the SUM and XOR. So in the example I mentioned the answer 4 is enough. I don't need to know which pairs satisfy them.

I took this problem from here.

I checked for an answer here. It provides an O(n) solution which is not enough.

There is an Editorial that provides the solution on this problem. It can be found here. (Look for the solution of 627A)

The problem is that I can't understand the solution. From what I could sum up they used a formula like this,
(If there are two numbers a and b) then, a+b = (a XOR b) + (a AND b)*2

How do I arrive to that? The rest of the steps are unclear to me.

If anyone could provide an idea on how to solve this or explain their solution, please help.

Upvotes: 19

Views: 45447

Answers (2)

Emil Vikström
Emil Vikström

Reputation: 91942

a AND b are the bits that are in both of the numbers. So these are doubled in the sum. a XOR b are the bits that are only present in one of the numbers so these should only be counted once in the sum.

Here is an example:

  • a = 4 = 1*2^2 + 0*2^1 + 0*2^0 (or just 100)
  • b = 13 = 1*2^3 + 1*2^2 + 0*2^1 + 1*2^0 (or just 1101)
  • a + b = (1*2^2 + 0*2^1 + 0*2^0) + (1*2^3 + 1*2^2 + 0*2^1 + 1*2^0) = 1*2^3 + 2*2^2 + 0*2^1 + 1*2^0

Note on the last line how the bit that is in both the numbers (2^2) is counted twice in the sum while the rest are only counted once!

To solve your problem you need to find all pairs (a, b) that adds up to the sum. What you want to do is this:

  1. Subtract the XOR value from the SUM. You are left with 2*(a AND b).
  2. Divide by 2. You now have all the bits that should be set in both a and b.
  3. Since you have the XOR value you know exactly what bits should be set in exactly one of a and b, while the AND value you just calculated are the bits that should be set in both of them. So you list all permutations of setting the bits in a or b respectively.

To continue my previous example:

  • a AND b = 0100 (set in both always)
  • a XOR b = 1001 (we need to try all permutations of these)

We get these permutations as solution:

  • a = 0100 + 0000 = 0100, b = 0100 + 1001 = 1101 => (4, 13)
  • a = 0100 + 0001 = 0101, b = 0100 + 1000 = 1100 => (5, 12)
  • a = 0100 + 1000 = 1100, b = 0100 + 0001 = 0101 => (12, 5)
  • a = 0100 + 1001 = 1101, b = 0100 + 0000 = 0100 => (13, 4)

Upvotes: 5

dejvuth
dejvuth

Reputation: 7136

Think of a+b = (a XOR b) + (a AND b)*2 as exactly what happen when you do binary addition. From your example, a = 010 and b = 111:

 010
 111
 ---
1001 = 101 + 100

For each bit, you add bits from a and b (0+0=0, 0+1=1, 1+0=1, 1+1=0, which is exactly a XOR b plus the carry-in bit from the previous addition, i.e. if both previous bits for a and b are 1, then we add it also. This is exactly (a AND b)*2. (Remember that multiplication by 2 is a shift left.)

With that equation we can calculate a AND b.

Now to count the number you want, we look at each bits of a XOR b and a AND b one-by-one and multiply all possibilities. (Let me write a[i] for the i-th bit of a)

  • If a[i] XOR b[i] = 0 and a[i] AND b[i] = 0, then a[i] = b[i] = 0. Only one possibility for this bit.

  • If a[i] XOR b[i] = 0 and a[i] AND b[i] = 1, then a[i] = b[i] = 1. Only one possibility for this bit.

  • If a[i] XOR b[i] = 1 and a[i] AND b[i] = 0, then a[i] = 1 and b[i] = 0 or vice versa. Two possibilities.

  • It's not possible to have a[i] XOR b[i] = 1 and a[i] AND b[i] = 1.

From your example, a XOR b = 101 and a AND b = 010. We have the answer 2*1*2 = 4.

Upvotes: 39

Related Questions