## fizzbuzzer

### Looking for good programming challenges?

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

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$.

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

Output Format
Print the number of beautiful quadruples.

Sample Input

1 2 3 4


Sample Output

11


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$:

int[] arr ={A,B,C,D};
Arrays.sort(arr);
A = arr;
B = arr;
C = arr;
D = arr;


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: 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$:

final int MAX = 3000;
int[] total = new int[MAX + 1];
for (int a = 1; a <= A; a++) {
for (int b = a; b <= B; b++) {
total[b] += 1;
}
}
for (int i = 1; i <= MAX; i++) {
total[i] += total[i - 1];
}


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$:

final int MAX_XOR = 4096;
int[][] count = new int[MAX + 1][MAX_XOR + 1];
for (int a = 1; a <= A; a++) {
for (int b = a; b <= B; b++) {
count[b][a ^ b] += 1;
}
}
for (int i = 0; i <= MAX_XOR; i++) {
for (int b = 1; b <= MAX; b++) {
count[b][i] += count[b - 1][i];
}
}


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]$

long ans = 0;
for (int c = 1; c <= C; c++) {
for (int d = c; d <= D; d++) {
ans += (total[c] - count[c][c ^ d]);
}
}


The full code is listed below.

Full code

public class BeautifulQuadruples {
private static long solve(int A, int B, int C, int D) {
final int MAX = 3000;
final int MAX_XOR = 4096;

// Sort A, B, C, D in ascending order
int[] arr = {A, B, C, D};
Arrays.sort(arr);
A = arr;
B = arr;
C = arr;
D = arr;

// total[b] holds the number of pairs {a,b} such that a≤b with 1≤a≤A and 1≤b≤B
int[] total = new int[MAX + 1];
for (int a = 1; a <= A; a++) {
for (int b = a; b <= B; b++) {
total[b] += 1;
}
}
for (int i = 1; i <= MAX; i++) {
total[i] += total[i - 1];
}

// count[B][x] holds the number of pairs {a,b} such that a≤b and a⊕b=x with 1≤a≤A, 1≤b≤B
// Note the maximum XOR value we can get is 4096. This is because, 3000 is 12 bits, and maximum value is when all
// 12 bits are set, which is 2^12 = 4096
int[][] count = new int[MAX + 1][MAX_XOR + 1];
for (int a = 1; a <= A; a++) {
for (int b = a; b <= B; b++) {
count[b][a ^ b] += 1;
}
}
for (int i = 0; i <= MAX_XOR; i++) {
for (int b = 1; b <= MAX; b++) {
count[b][i] += count[b - 1][i];
}
}

long ans = 0;
for (int c = 1; c <= C; c++) {
for (int d = c; d <= D; d++) {
ans += (total[c] - count[c][c ^ d]);
}
}

return ans;
}

public static void main(String[] args) throws FileNotFoundException {
System.setIn(new FileInputStream(System.getProperty("user.home") + "/" + "in.txt"));
Scanner in = new Scanner(System.in);

int a = in.nextInt();
int b = in.nextInt();
int c = in.nextInt();
int d = in.nextInt();

System.out.println(solve(a, b, c, d));
}
}