There are 4 brothers in a home. Each of them
has 2000, 5000, 6000, 8000 in their saving accounts respectively. Each of them
will spend this amount of money averagely for several months respectively. One
day, the electricity trips has lead to the damage of their only TV in home.
They decided to gather money based on their respective affordability of monthly disposable to buy a new TV. They are not rushing to buy it immediate because a new TV cost
about $2500. So, how many months these 4 brothers can delaying the new TV
purchase before they are running out of money in saving accounts? (Hints , the
sum of contribution of each brother from monthly average disposable saving
amounts must be enough to afford the new TV)
Example Answer
public int SmallestDivisor(List<int> nums, int threshold)
{
int left = 1, right = nums.Count ;
int ans = 0;
while (left <= right)
{
int mid = left + (right - left) / 2;
int sum = 0;
for (int i = 0; i < nums.Count; i++)
{
if (nums[i] % mid == 0)
{
sum += (nums[i] / mid);
}
else
{
sum += (nums[i] / mid) + 1;
}
}
if (sum > threshold)
{
left = mid + 1;
}
else
{
ans = mid;
right = mid - 1;
}
}
return ans;
}
Java
Java
package BSTest;
import java.util.Arrays;
public class Test {
public static void main(String[] args) {
// TODO Auto-generated
method stub
Solution
sol = new Solution();
int threshold = 5;
//int[] nums = new int[5];
int[] nums = new int[] {13, 16, 17, 18,
2, 4, 7, 8, 9, 11};
Arrays.sort(nums);
int answer = 0;
answer = sol.smallestDivisor(nums, threshold);
}
}
class Solution {
public int smallestDivisor(int[] nums, int threshold) {
if (nums == null || nums.length == 0) {
return 0;
}
int max = Arrays.stream(nums).max().orElse(0);
int start = 1;
int end = max;
while (start + 1 < end) {
int mid = start + (end - start) / 2;
int divSum = getDivSum(nums, mid);
if (divSum <= threshold) {
end = mid;
} else {
start = mid;
}
}
if (getDivSum(nums, start) <= threshold) {
return start;
} else {
return end;
}
}
private int getDivSum(int[] nums, int div) {
int sum = 0;
for (int num : nums) {
sum += num / div;
if (num % div > 0) {
sum++;
}
}
return sum;
}
}
No comments:
Post a Comment