7320: CodeChef JOINTXOR - Joint XOR
[Creator : ]
Description
Chef has a binary string $S$ of length $N$. Chef wants to find two substrings of equal length, such that their bitwise XOR is maximised.
Formally, Chef wants to find $L_1, R_1, L_2$, and $R_2$ such that:
Note that a substring is formed by deleting some (possibly zero) characters from the beginning and some (possibly zero) characters from the end of the string.
Formally, Chef wants to find $L_1, R_1, L_2$, and $R_2$ such that:
- $1 \le L_1 \le R_1 \le N$ and $1 \le L_2 \le R_2 \le N$
- $|R_1 - L_1 + 1| = |R_2 - L_2 + 1|$, that is, the substrings have equal length;
- $S_{L_1 \dots R_1} \oplus S_{L_2 \dots R_2}$ is maximised, where $\oplus$ is the bitwise XOR operation.
Note that a substring is formed by deleting some (possibly zero) characters from the beginning and some (possibly zero) characters from the end of the string.
Input
The first line of input will contain a single integer $T$, denoting the number of test cases.
Each test case consists of multiple lines of input.
The first line of each test case contains a single integer $N$ denoting the length of string $S$.
The second line of each test case contains a binary string $S$ of length $N$ containing 0s and 1s only.
Each test case consists of multiple lines of input.
The first line of each test case contains a single integer $N$ denoting the length of string $S$.
The second line of each test case contains a binary string $S$ of length $N$ containing 0s and 1s only.
Output
For each test case, output the maximum XOR value in decimal notation. Since the value can be large, output it module $10^9+7$.
Constraints
$1≤T≤10^5$
$2 \leq N \leq 2 \cdot 10^6$
S contains 0 and 1 only.
The sum of N over all test cases won't exceed $2 \cdot 10^6$.
$2 \leq N \leq 2 \cdot 10^6$
S contains 0 and 1 only.
The sum of N over all test cases won't exceed $2 \cdot 10^6$.
Sample 1 Input
3
4
1010
5
11111
3
011
Sample 1 Output
7
0
2
Test case 1: We can choose $L_1 = 1, R_1 = 3, L_2 = 2$, and $R_2 = 4$. Thus, the chosen substrings are 101 and 010. The XOR of these substrings is 111 whose decimal equivalent is 7.
Test case 2: We can choose $L_1 = 2, R_1 = 2, L_2 = 4$, and $R_2 = 4$. Thus, the chosen substrings are 1 and 1. The XOR of these substrings is 0 whose decimal equivalent is 0.
Test case 3: We can choose $L_1 = 1, R_1 = 2, L_2 = 2$, and $R_2 = 3$. Thus, the chosen substrings are 01 and 11. The XOR of these substrings is 10 whose decimal equivalent is 2.
Test case 2: We can choose $L_1 = 2, R_1 = 2, L_2 = 4$, and $R_2 = 4$. Thus, the chosen substrings are 1 and 1. The XOR of these substrings is 0 whose decimal equivalent is 0.
Test case 3: We can choose $L_1 = 1, R_1 = 2, L_2 = 2$, and $R_2 = 3$. Thus, the chosen substrings are 01 and 11. The XOR of these substrings is 10 whose decimal equivalent is 2.