hi, can anyone please tell whats the logic behind using bitwise or.
int main()
{
//int t;
int n,maxmin;
fastIO;
ll x=0,y=0,pre;
cin>>n;
ll z;
for(int i=0;i<n;i++)
{
x=0;
pre=0;
for(int j=0;j<n;j++)
{
cin>>z;
if(z!=-1)
x=pre|z;
pre=x;
}
//cout<<x<<" “;
y+=x;
}
cout<<y<<”\n";
}
Consider a 5 X 5 input - A :
A[0][1] = a[0] & a[1].
For each set bit in A[0][1] we can conclude that the respective bit is also set in a[0] and a[1].
Similarly, from A[0][2],A[0][3] and A[0][4] we can get all the set bits of A[0].
The best way to calculate the set bits in A[0] is to perform OR operation on the first row (except A[0][0]).
Why ?
Consider the kth bit of A[0] :
If it is not set (0) : then the kth bit of all the elements of the first row will be unset. Thus after doing OR the kth bit will remain unset.
If it is set (1) : then the kth bit of at least one of the elements of the first row hast to be set. Thus, after doing OR, the kth bit will be set(speciality of OR).
Contradiction : -1 5 5 5 5(only first row)
here after doing OR , A[0] = 5 = 0101
but A[0] can be 13(1101), *29(11101), larger value…
Since, we are required to calculate the minimum value of A[0], 5 will work.
Similar proof can be done for all rows.
Hope it is clear.
thanks!! it helped me a lot.
Thank you…helped me too