Binary Search Question

Question

Hi

I have come across a problem and could understand that it is rated to binary search.

Please find code and details of same in code itself as below :
https://sololearn.com/compiler-playground/c14n6lE8F5IR/?ref=app

Can someone point out why I am getting answer as 0 and not 1? What is wrong with my implementation ? Is it something wrong in bool function?

Answer 1

The reason why you got output 0 instead of 1 for the second example is that your isAllowed function only returns true if the number of required banks is exactly equal to the number of approved banks. However, in the second example, you have 5 approved banks but only 4 required banks, so the function returns false for any value of perBank. This causes the binary search to fail and return 0 as the answer.

To fix this, you need to change the condition in your isAllowed function to return true if the number of required banks is less than or equal to the number of approved banks. This way, you can handle the cases where there are more approved banks than required banks, and still maximize the minimum number of persons per bank.
Here is the modified code:
https://sololearn.com/compiler-playground/c0u0ARY95fon/?ref=app

Answer 2

Thanks for analysis and response. But it is not what is expected.

Output cannot be 10 for the example you have on your code.

Answer 3

Oh, What should be the output?

Answer 4

vector<int> populations{8,7,1,5,5,10,10,1,5,3};
int n = 17;

Village 0 with population 8 can have 1 bank with 8 people

Village 2 with population 1 can have 1 bank with 1 people

So output is 1 as it is min among all banks.

As one Village has min one bank, we can not increase ans more than 1