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 1
1000000000 499999985 2 1
1000000000 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

2
2.00004

In python3

>>> 1000000000/499999986.0
2.0000000560000015
>>> 1000000000/499990000.0
2.000040000800016

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