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;

The output is

2
2.00004

In python3

>>> 1000000000/499999986.0

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

Data Scientist/MLE/SWE @takemobi