# Binary search

1760. Minimum Limit of Balls in a Bag

Python works

`class Solution:    def minimumSize(self, nums: List[int], maxOperations: int) -> int:        l, r = 1, int(1e9)        def good(m):            return sum(math.ceil(n/m) - 1 for n in nums) <= maxOperations        while l < r:            m = (l + r) // 2;            if good(m):                r = m            else:                l = m + 1        return l`

C++ fails in case b

`class Solution {public:    bool good(vector<int>& nums, int maxOperation, int m){        long long operation = 0;        for (auto x :nums ){            long long a = (x - 1) / m; // case a            long long b = ceil(x/float(m)) - 1; // case b            if (a != b) cout<<a<<" "<<b<<endl;            operation += b;// choose b fails            if (operation > maxOperation)return false;        }        return true;    }    int minimumSize(vector<int>& nums, int maxOperations) {        int l = 1, r = 1e9;        while (l < r) {            int m = (l + r ) / 2;            if (m>=101851 && m < 101860)cout<<m<<endl;            auto ret = good(nums,maxOperations, m);             if (m>=101851 && m < 101860)cout <<ret<<endl;            if (ret){                r = m;            } else {                l = m + 1;            }        }        return l;    }};`

If we check this example,

[1000000000]

1

We get

`1000000000 499999986 2 11000000000 499999985 2 11000000000 499999984 2 1`

Should be an precision problem. Change the code to case c or simplely change the date type from float to double, the code can get passed.

`class Solution {public:    bool good(vector<int>& nums, int maxOperation, int m){        long long operation = 0;        for (auto x :nums ){            long long a = (x - 1) / m;            long long b = ceil(x/float(m)) - 1;            long long c = x%m==0 ? x/m - 1 : x/m;            long long d = ceil(x/double(m)) - 1;            if (a != d) cout<<a<<" "<<d<<endl;            operation += d;            if (operation > maxOperation)return false;        }        return true;    }    int minimumSize(vector<int>& nums, int maxOperations) {        int l = 1, r = 1e9;        while (l < r) {            int m = (l + r ) / 2;            if (m>=101851 && m < 101860)cout<<m<<endl;            auto ret = good(nums,maxOperations, m);             if (m>=101851 && m < 101860)cout <<ret<<endl;            if (ret){                r = m;            } else {                l = m + 1;            }        }        return l;    }};`

In order to verify, we can test the following code

`#include <iostream>using namespace std;int main(){    float ret = 1000000000/499999986.0;    cout<<ret<<endl;    ret = 1000000000/499990000.0;    cout<<ret<<endl;    return 0;}`

The output is

`22.00004`

In python3

`>>> 1000000000/499999986.02.0000000560000015>>> 1000000000/499990000.02.000040000800016`

If you want to know more about the precision of the floating point number, read this classical article.

Data Scientist/MLE/SWE @takemobi

## More from Jimmy Shen

Data Scientist/MLE/SWE @takemobi