Programming interview questions

### Looking for good programming/interview questions?

Use the search below to find our solutions for selected questions!

Problem statement
We call an quadruple of positive integers, $(W, X, Y, Z)$, beautiful if the following condition is true:

$W \oplus X \oplus Y \oplus Z \ne 0$

Note: $\oplus$ is the bitwise XOR operator.

Given $A, B, C$ and $D$, count the number of beautiful quadruples of the form $(W, X, Y, Z)$ where the following constraints hold:

$1 \le W \le A$
$1 \le X \le B$
$1 \le Y \le C$
$1 \le Z \le D$

When you count the number of beautiful quadruples, you should consider two quadruples as same if the following are true:
– They contain same integers.
– Number of times each integers occur in the quadruple is same.

For example $(1, 1, 1, 2)$ and $(1, 1, 2, 1)$ should be considered as same.

Input Format
A single line with four space-separated integers describing the respective values of $A, B, C$ and $D$.

Constraints
$1 \le A, B, C, D \le 3000$

Output Format
Print the number of beautiful quadruples.

Sample Input

Sample Output

Explanation
There are $11$ beautiful quadruples for this input:
$(1,1,1,2)$
$(1,1,1,3)$
$(1,1,1,4)$
$(1,1,2,3)$
$(1,1,2,4)$
$(1,1,3,4)$
$(1,2,2,2)$
$(1,2,2,3)$
$(1,2,2,4)$
$(1,2,3,3)$
$(1,2,3,4)$

Thus, we print $11$ as our output.
Note that $(1, 1, 1, 2)$ is same as $(1, 1, 2, 1)$ .

Solution
Since the order of the integers in a quadruple does not matter we can sort our input values such that $A \le B \le C \le D$:

We will then solve it for the first half of the quadruple $(a,b,c,d)$. For that we define the following arrays:
total = new int[3001]: total[B] holds the number of pairs $\{ a,b\}$ such that $a \le b$ with $1 \le a \le A$ and $1 \le b \le B$:

count = new int[3000 + 1][4096 + 1]: count[B][x] holds the number of pairs $\{a,b\}$ such that $a \le b$ and $a \oplus b = x$ with $1 \le a \le A$ and $1 \le b \le B$:

Note here that the maximum XOR value achievable is $4096$ since $1 \le A, B, C, D \le 3000$ (12 bits).

We can now go ahead and use total and count to find our solution. Remember we sorted our $A \le B \le C \le D$ so that we count our quadruples $(a,b,c,d)$ such that $a \le b \le c \le d$.

For the second half of $(a,b,c,d)$ we have $\{c,d\}$ with $1 \le c \le C$ and $1 \le d \le D$. Let $c \oplus d = y$. We know that $a \oplus b \oplus c \oplus d = 0$ if $a \oplus b = y$. We know that we have a total of total[c] pairs $\{a,b\}$ with $a \le b$ and $1 \le b \le c$. We want to exclude the pairs that have $a \oplus b = y$. There are count[c][y] pairs $\{a,b\}$ that combined with $\{c,d\}$ result to $0$. So from total[c] we have to exclude count[c][y] and do this for all possible $c$ and $d$:
$\sum_{c=1}^{C}\sum_{d=1}^{D}total[c]-count[c][c \oplus d]$

The full code is listed below.

Full code