Programming interview questions

Looking for good programming/interview questions?

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

Beautiful quadruples challenge

Sharing is caring!

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.

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

Output Format
Print the number of beautiful quadruples.

Sample Input

Sample Output

There are 11 beautiful quadruples for this input:

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

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