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?
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
GCD Groups
You are viewing a single comment's thread. Return to all comments →
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?