You have two binary arrays A and B.
In one move, you can pick three indices 1 \leq i \lt j \lt k \leq N, and set A_j := A_i \mid A_j \mid A_k.
Find out whether A can be made equal to B.
EXPLANATION:
The operation we perform has the following properties:
It cannot turn a 1 into a 0 (if A_j = 1, then no matter what i and k we choose A_i\mid A_j \mid A_k = 1 will hold).
To turn a 0 into a 1, the array must itself contain a 1 somewhere (if A_j = 0, then for A_i \mid A_j \mid A_k = 1 to hold, either A_i = 1 or A_k = 1 must be true).
It cannot change A_1 and A_N, since j is strictly larger than 1 and strictly less than N.
This gives us a set of checks for when making A cannot be made equal to B:
If A_1 \neq B_1 or A_N \neq B_N, the answer is “No”.
If A_i = 1 and B_i = 0 for some i, the answer is “No”.
If A_i = 0 and B_i = 1 for some i, and A doesn’t contain any ones, the answer is “No”.
If the number of ones in A is computed first, this check can be done in \mathcal{O}(1) for each index, leading to \mathcal{O}(N) time overall.
If none of the “No” conditions trigger, the answer is “Yes”.
TIME COMPLEXITY
\mathcal{O}(N) per test case.
CODE:
Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
ans = 'Yes'
ones = a.count(1)
for i in range(n):
if a[i] > b[i]: ans = 'No'
elif a[i] < b[i] and ones == 0: ans = 'No'
if a[0] != b[0] or a[-1] != b[-1]: ans = 'No'
print(ans)
then the answer will be no because when you try to convert A[2] = 0 to A[2] = 1 using the last element of A then A[3] will be converted to 1. Now A[3] can not be converted to 0 so the answer will be no but your code is returning yes.
a corner case is not check here , when B[i] is 0 and A[i] is also 0 we need to check if a 0 is present in the array A before the index and also after the index , if not present we have to return NO but it is not checked , please clarify
/* Name of the class has to be “Main” only if the class is public. */
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
Scanner s = new Scanner(System.in);
long t = s.nextLong();
while(t-- > 0){
long n = s.nextLong();
int countA=0;
ll n;
cin >> n;
vector<char> a(n, '0'), b(n, '0');
bool flag = false;
// a
for (int i = 0; i < n; i++)
{
cin >> a[i];
}
// b
for (int i = 0; i < n; i++)
{
cin >> b[i];
// check if a is 1 and b is 0, as we can't change 1 to 0 using or
if (a[i] == '1' && b[i] == '0')
{
flag = true;
}
}
if (flag)
{
cout << "NO\n";
continue;
}
// checking for corner as there will no i for 0th position and k for nth position and if in that case a and b are different then no
if ((b[n - 1] == '1' && a[n - 1] == '0') || (b[0] == '1' && a[0] == '0'))
{
cout << "NO\n";
continue;
}
// storing numbers of ones for front and back fashion so that we know for every position that there is ones available in front or back to convert it into 1.
vector<int> ones_f(n, 0), ones_b(n, 0);
for (int i = n - 1; i >= 0; i--)
{
if (a[i] == '1')
{
ones_b[i] = 1;
ones_f[i] = 1;
}
}
for (int i = 1; i < n; i++)
{
ones_f[i] += ones_f[i - 1];
}
for (int i = n - 2; i >= 0; i--)
{
ones_b[i] += ones_b[i + 1];
}
for (int i = 0; i < n; i++)
{
if (a[i] == '0' && b[i] == '1' && ones_f[i] == 0 && ones_b[i] == 0)
{
flag = true;
break;
}
}
if (flag)
{
cout << "NO\n";
}
else
{
cout << "YES\n";
}