Warm-up Equation (Editorial)

Group 1: a < b.

obviously x+y \ge x \, | \, y

so a \ge b therefore, there are no solutions hence, output should be $-1$

Group 2: a, b \le 10^3, g = 0.

Since the numbers $x$ , $y$ are non-negative, it means that x , y \le a

We can iterate through the numbers $x$ , $y$ if their sum is equal to $a$ and bitwise OR is equal to $b$

the code will look something like this

int count = 0; 
for (int x = 0; x <= a; x++) 
{
	for (int y = 0; y <= a; y++) 
        {
		if (((x + y) == a) and ((x | y) == b)) 
                {
			count++;
		}
	}
}
cout << count;

Group 3: a, b \le 10^3.

the solution is similar to the solution in the second group, but we also need to calculate the minimum distance

Group 4: a, b \le 10^6, g = 0.

Let's iterate only through $x$ , and calculate $y$ from the equation x + y = a \implies y = a - x

the code will look something like this

int count = 0;

for (int x = 0; x <= a; x++)
{
	int y = a - x;

	if (((x + y) == a) and ((x | y) == b))
	{
		count++;
	}
}

cout << count;

Group 5: a, b \le 10^6.

the solution is similar to the solution in the fourth group, but we also need to calculate the minimum distance

Group 6: a, b \le 10^{18}, g = 0.

$\oplus$ - denotes bitwise exclusive OR

then we can find the bitwise exclusive OR of the numbers $x$ , $y$ ; $x$ $\oplus$ $y$ = 2*b - a

If the bitwise exclusive OR < 0 then the answer is $0$

now let's go through all the bits

1) if the bit is present in the bitwise OR and also in the bitwise exclusive OR then the bit can be in both $x$ and $y$ therefore the number of ways is multiplied by 2

2) if the bit is present in the bitwise OR and not in the bitwise exclusive OR then the bit will be in both numbers and the number of ways does not change

3) if the bit is not present in the bitwise OR and not in the bitwise exclusive OR then the bit will not be in both numbers and the number of ways does not change

4) if the bit is not present in the bitwise OR and present in the bitwise exclusive OR this case is not possible because the bit is present in one of the numbers but not in the bitwise OR

the code will look something like this

long long xor_ = 2*b - a;
long long or_ = b;
long long count = 1;

if (xor_ < 0)
{
	cout << 0;
	return 0;
}
for (int i = 0; i < 61; i++)
{
	if (((or_ & (1ll << i)) == 0) and ((xor_ & (1ll << i)) != 0))
	{
		count = 0;
	}

	if (((or_ & (1ll << i)) != 0) and ((xor_ & (1ll << i)) != 0))
	{
		count *= 2;
	}
}

cout << count;

Group 7: a, b \le 10^{18} (no additional constraints).

when g = 0 , the solution is the same as the solution of the 6th group

when g = 1 , we need to find the minimum distance

Consider all the bits from the 6th group, we know that the only undefined bits are the bits where the bit can be in either one of the numbers or in the other

Now it can be noticed that the number in which the maximum undefined bit will be the maximum of the numbers

then in order for the distance between the numbers to be minimum all the other undefined bits should be in the other number

the code will look something like this

long long a , b , g;
cin >> a >> b >> g;

long long xor_ = 2*b - a;
long long or_ = b;
long long count = 1;
long long x = 0;
long long y = 0;

if (xor_ < 0)
{
	if (g == 0)
		cout << 0;
	else
		cout << 0 << endl << -1;
	return 0;
}
for (int i = 60; i >= 0; i--)
{
	if (((or_ & (1ll << i)) == 0) and ((xor_ & (1ll << i)) != 0))
	{
		if (g == 0)
			cout << 0;
		else
			cout << 0 << endl << -1;
		return 0;
	}

	if (((or_ & (1ll << i)) != 0) and ((xor_ & (1ll << i)) != 0))
	{
		count *= 2;
		if (x < y)
			x += (1ll << i);
		else
			y += (1ll << i);
	}

}
if (g == 0)
	cout << count;
else
	cout << count << endl << abs(x - y);