GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

Wednesday 26 October 2022

[Solution] Joint XOR CodeChef Solution | Solution CodeChef



Problem

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:

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

Output the maximum XOR value in decimal notation. Since the value can be large, output it module 10^9+7.

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 Format

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

Output Format

For each test case, output the maximum XOR value in decimal notation. Since the value can be large, output it module 10^9+7.


Solution Click Below:-  👉CLICK HERE👈
👇👇👇👇👇

Explanation:

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.

No comments:

Post a Comment