Daily Coding Problem #332: Relationship between SUM, XOR and AND of Two Numbers

Problem Definition

Given integers $M$ and $N$, write a program that counts how many positive integer pairs $(a, b)$ satisfy the following conditions:

1. $a + b = M$
2. $a\ XOR\ b = N$

Solution

$\mathtt{Solution\ REFERENCE}$ @ StackOverflow

Implementation

	import java.io.*;
	import java.util.Scanner;
	class Solution {
	public static void main (String[] args) {
	Scanner sc = new Scanner(System.in);
	long X = sc.nextLong();
	long S = sc.nextLong();
	long A = (S-X);
	if (A%2 == 1) {
	System.out.println("none");
	return;
	}
	A = A >> 1;
	int answers = 1;
	for(int i = 1; i <= 64; i++) {
	int xi =(int) (X & 1); // obtain LSB of XOR
	int ai = (int) (A & 1); // obtain LSB of AND
	// XOR bit is 1, AND bit is 0 which means two number bits can be either 0 and 1 OR 1 and 0
	if (xi == 1 && ai == 0) answers *= 2;
	// XOR bit is 1, AND bit is 1 , which means there can't be such numbers
	else if (xi == 1 && ai == 1) {
	System.out.println("none");
	return;
	}
	// XOR bit is 0, AND bit is 0, there can be only one choice: 0 and 0,
	// XOR bit is 0, AND bit is 1, there can be only one choice: 1 and 1
	X = X >> 1;
	A = A >> 1;
	}
	System.out.println(answers + " Pairs");
	}
	}

view raw Solution.java hosted with ❤ by GitHub

Complexity

This implementation iterates through all the bits in $XOR$ and $AND$. If $N$ be the number of bits, then the time complexity is $\cal{O(N)}$.

---

---

---