Table of Contents
We Are Discuss About CODECHEF SOLUTION
Light The Bulb CodeChef Solution
Chef has a kitchen with a bulb and � switches. The bulb will only light up if the � switches are in a specific order, as given by a binary string � of size �.
In this binary string,
0 at the ��ℎ position represents that the ��ℎ switch is
1 means that the switch is
Initially, Chef has the switches in the state represented by the binary string � of length �.
Chef can light up the bulb by performing the given operation exactly two times. The operation is defined as follows:
- Choose a substring �[�,�] where 1≤�≤�≤�, and flip all characters in the string. Note that you flip a
A sequence of two operations �[�1,�2] and �[�3,�4] is considered different from a sequence of operations �[�1,�2] and �[�3,�4] if there exists a � such that ��≠��, where (1≤�≤4).
Your task is to find the number of ways Chef can perform these two operations to light up the bulb.
- The first line of input will contain a single integer �, which denotes the number of test cases.
- Each test case consists of multiple lines of input:
- The first line of each test case contains a space-separated integer �, representing the number of switches.
- The following two lines contain binary strings, � and �, representing the required and initial switch arrangements, respectively.
For each test case, output on a new line, the number of ways Chef can perform these two operations to light up the bulb.
- � and � consist of
- The sum of � across all test cases won’t exceed 106.
2 4 0111 1010 3 010 111
Test case 1: To light the bulb, the required arrangement for bulbs needs to be
0111. The initial arrangement of switches is
1010. There are 6 ways to light the bulb:
- Choose substring [1,2], making �=0110 and then substring [4,4], making �=0111.
- Choose substring [4,4], making �=1011 and then substring [1,2], making �=0111.
- Choose substring [1,3], making �=0100 and then substring [3,4], making �=0111.
- Choose substring [3,4], making �=1001 and then substring [1,3], making �=0111.
- Choose substring [3,3], making �=1000 and then substring [1,4], making �=0111.
- Choose substring [1,4], making �=0101 and then substring [3,3], making �=0111.
6 digit code appear after 69 seconds.