We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
if (max(0,n/2-pr)+max(0,n/2-dr)==ob) da++;"
Here we are basically considering the case that if we are able to divide the array then each group will have n/2 elements. Now group will have gcd p and another will have gcd q. Now from n/2 elements in first group if we remove the elements which are only divisible by p we will have (n/2-pr) elements which are divisible by both p and q. Similarly for the second group also. If we sum these up we will get the number of elements that are divisible by both. That value here is ob.
But I am just not sure why are we taking max(0,n/2-pr) is it necessary ? Wouldn't just n-pr-dr==ob be sufficient?
if (max(0,n/2-pr)+max(0,n/2-dr)==ob) da++;" Here we are basically considering the case that if we are able to divide the array then each group will have n/2 elements. Now group will have gcd p and another will have gcd q. Now from n/2 elements in first group if we remove the elements which are only divisible by p we will have (n/2-pr) elements which are divisible by both p and q. Similarly for the second group also. If we sum these up we will get the number of elements that are divisible by both. That value here is ob.
But I am just not sure why are we taking max(0,n/2-pr) is it necessary ? Wouldn't just n-pr-dr==ob be sufficient?
in the first solution given in the editorial ,I wante to ask the line" if (max(0,n/2-pr)+max(0,n/2-dr)==ob) da++;"
should instead be if (max(0,n/2-pr)+max(0,n/2-dr)<=ob) da++;
hello