B. Flip the Bits | Codeforces Round 712 (Div. 2)

There is a binary string $a$ of length $n$ . In one operation, you can select any prefix of $a$ with an equal number of $0$ and $1$ symbols. Then all symbols in the prefix are inverted: each $0$ becomes $1$ and each $1$ becomes $0$ .

For example, suppose $a = 0111010000$ .

In the first operation, we can select the prefix of length $8$ since it has four $0$ 's and four $1$ 's: $[01110100] 00 \to [10001011] 00$ .
In the second operation, we can select the prefix of length $2$ since it has one $0$ and one $1$ : $[10] 00101100 \to [01] 00101100$ .
It is illegal to select the prefix of length $4$ for the third operation, because it has three $0$ 's and one $1$ .

Can you transform the string $a$ into the string $b$ using some finite number of operations (possibly, none)?

Input

The first line contains a single integer $t$ ( $1 \leq t \leq 10^{4}$ ) — the number of test cases.

The first line of each test case contains a single integer $n$ ( $1 \leq n \leq 3 \cdot 10^{5}$ ) — the length of the strings $a$ and $b$ .

The following two lines contain strings $a$ and $b$ of length $n$ , consisting of symbols $0$ and $1$ .

The sum of $n$ across all test cases does not exceed $3 \cdot 10^{5}$ .

Output

For each test case, output "YES" if it is possible to transform $a$ into $b$ , or "NO" if it is impossible. You can print each letter in any case (upper or lower).

Example
inputCopy
5
10
0111010000
0100101100
4
0000
0000
3
001
000
12
010101010101
100110011010
6
000111
110100
outputCopy
YES
YES
NO
YES
NO

Note

The first test case is shown in the statement.

In the second test case, we transform $a$ into $b$ by using zero operations.

In the third test case, there is no legal operation, so it is impossible to transform $a$ into $b$ .

In the fourth test case, here is one such transformation:

Select the length $2$ prefix to get $100101010101$ .
Select the length $12$ prefix to get $011010101010$ .
Select the length $8$ prefix to get $100101011010$ .
Select the length $4$ prefix to get $011001011010$ .
Select the length $6$ prefix to get $100110011010$ .

In the fifth test case, the only legal operation is to transform $a$ into $111000$ . From there, the only legal operation is to return to the string we started with, so we cannot transform $a$ into $b$ .

Solution :

We know that we always have to choose prefixes so we will start from the last and check if the current char is equal to the char in string b. If it is we will continue else we need to check whether we can choose a prefix and flip the bits.

Now if we flip the bits then all the bits before the current position will also get flipped, we will store this in our chng variable. If this is odd then we will flip the bit else not.

void solve() {

int n;
cin>>n;

string a,b;
cin>>a>>b;

vector<int>v;
int zero=0,one=0;

// to keep the difference of number of zero and one 
for(int i=0; i<n; i++){
    a[i] == '1' ? ++one : ++zero;
    v.push_back(abs(one-zero));
}

int chng = 0;
for (int i = n - 1; i >= 0; i--)
{
// check whether this bit can flipped or not
    if(chng%2==1) a[i] == '1' ? a[i] = '0' : a[i] = '1';
    if(a[i]!=b[i]){
        if(v[i]==0){
            chng ++;
        }
        else {
            cout<<"NO\n";
            return;
        }
    }
}

cout<<"YES\n";

}