Search Blogs

Showing results for "Ceiling Division"

Found 2 results

LeetCode 1283 — Find the Smallest Divisor Given a Threshold | Binary Search on Answer Explained

🚀 Try This Problem First!Before reading the solution, attempt it yourself on LeetCode — you'll retain the concept far better.🔗 Problem Link: https://leetcode.com/problems/find-the-smallest-divisor-given-a-threshold/Understanding the ProblemYou are given an array of integers nums and an integer threshold. You must choose a positive integer divisor, divide every element of the array by it (rounding up to the nearest integer), sum all the results, and make sure that sum is ≤ threshold.Goal: Find the smallest possible divisor that keeps the sum within the threshold.Important detail — Ceiling Division: Every division rounds up, not down. So 7 ÷ 3 = 3 (not 2), and 10 ÷ 2 = 5.Constraints:1 ≤ nums.length ≤ 5 × 10⁴1 ≤ nums[i] ≤ 10⁶nums.length ≤ threshold ≤ 10⁶Two Key Observations (Before Writing a Single Line of Code)Minimum possible divisor: The divisor must be at least 1. Dividing by anything less than 1 isn't a positive integer. So:low = 1Maximum possible divisor: If divisor = max(nums), then every element divided by it gives at most 1 (due to ceiling), so the sum equals nums.length, which is always ≤ threshold (guaranteed by constraints). So:high = max(nums)Our answer lies in the range [1, max(nums)]. This is the search space for Binary Search.Intuition — Why Binary Search?Ask yourself: what happens as the divisor increases?As divisor gets larger, each divided value gets smaller (or stays the same), so the total sum decreases or stays the same. This is a monotonic relationship — the green flag for Binary Search on the Answer.Instead of trying every divisor from 1 to max(nums), we binary search over divisor values. For each candidate mid, we ask:"Does dividing all elements by mid (ceiling) give a sum ≤ threshold?"This feasibility check runs in O(N), making the whole approach O(N log(max(nums))).The Feasibility Check — Ceiling Sum SimulationGiven a divisor mid, compute the sum of ⌈arr[i] / mid⌉ for all elements. If the total sum ≤ threshold, then mid is a valid divisor.In Java, ceiling division of integers is done as:Math.ceil((double) arr[i] / mid)Binary Search StrategyIf canDivide(mid) is true → mid might be the answer, but try smaller. Set ans = mid, high = mid - 1.If canDivide(mid) is false → divisor is too small, increase it. Set low = mid + 1.Dry Run — Example 1 (Step by Step)Input: nums = [1, 2, 5, 9], threshold = 6We start with low = 1 and high = 9 (max element in array).Iteration 1: mid = 1 + (9 - 1) / 2 = 5Compute ceiling sum with divisor 5: ⌈1/5⌉ + ⌈2/5⌉ + ⌈5/5⌉ + ⌈9/5⌉ = 1 + 1 + 1 + 2 = 55 ≤ 6 → ✅ Valid. Record ans = 5, search smaller → high = 4.Iteration 2: mid = 1 + (4 - 1) / 2 = 2Compute ceiling sum with divisor 2: ⌈1/2⌉ + ⌈2/2⌉ + ⌈5/2⌉ + ⌈9/2⌉ = 1 + 1 + 3 + 5 = 1010 > 6 → ❌ Too large. Increase divisor → low = 3.Iteration 3: mid = 3 + (4 - 3) / 2 = 3Compute ceiling sum with divisor 3: ⌈1/3⌉ + ⌈2/3⌉ + ⌈5/3⌉ + ⌈9/3⌉ = 1 + 1 + 2 + 3 = 77 > 6 → ❌ Too large. Increase divisor → low = 4.Iteration 4: mid = 4 + (4 - 4) / 2 = 4Compute ceiling sum with divisor 4: ⌈1/4⌉ + ⌈2/4⌉ + ⌈5/4⌉ + ⌈9/4⌉ = 1 + 1 + 2 + 3 = 77 > 6 → ❌ Too large. Increase divisor → low = 5.Loop ends: low (5) > high (4). Binary search terminates.Output: ans = 5 ✅The Code Implementationclass Solution {/*** Feasibility Check (Helper Function)** Given a divisor 'mid', this function computes the ceiling sum of* all elements divided by 'mid' and checks if it is within threshold.** @param mid - candidate divisor to test* @param arr - input array* @param thresh - the allowed threshold for the sum* @return true if the ceiling division sum <= threshold, false otherwise*/public boolean canDivide(int mid, int[] arr, int thresh) {int sumOfDiv = 0;for (int i = 0; i < arr.length; i++) {// Ceiling division: Math.ceil(arr[i] / mid)// Cast to double to avoid integer division truncationsumOfDiv += Math.ceil((double) arr[i] / mid);}// If total sum is within threshold, this divisor is validreturn sumOfDiv <= thresh;}/*** Main Function — Binary Search on the Answer** Search range: [1, max(nums)]* - low = 1 → smallest valid positive divisor* - high = max(nums) → guarantees every ceil(num/divisor) = 1,* so sum = nums.length <= threshold (always valid)** @param nums - input array* @param threshold - maximum allowed sum after ceiling division* @return smallest divisor such that the ceiling division sum <= threshold*/public int smallestDivisor(int[] nums, int threshold) {int min = 1; // Lower bound: divisor starts at 1int max = Integer.MIN_VALUE; // Will become max(nums)int ans = 1;// Find the upper bound of binary search (max element)for (int a : nums) {max = Math.max(max, a);}// Binary Search over the divisor spacewhile (min <= max) {int mid = min + (max - min) / 2; // Safe midpoint, avoids overflowif (canDivide(mid, nums, threshold)) {// mid is valid — record it and try a smaller divisorans = mid;max = mid - 1;} else {// mid is too small — the sum exceeded threshold, go highermin = mid + 1;}}return ans; // Smallest valid divisor}}Code Walkthrough — Step by StepSetting bounds: We iterate through nums once to find max — this becomes our upper bound high. The lower bound low = 1 because divisors must be positive integers.Binary Search loop: We pick mid = min + (max - min) / 2 as the candidate divisor. We check if using mid as the divisor keeps the ceiling sum ≤ threshold.Feasibility helper (canDivide): For each element, we compute Math.ceil((double) arr[i] / mid) and accumulate the total. The cast to double is critical — without it, Java performs integer division (which truncates, not rounds up).Narrowing the search: If the sum is within threshold → record ans = mid, try smaller (max = mid - 1). If the sum exceeds threshold → divisor is too small, increase it (min = mid + 1).A Critical Bug to Watch Out For — The return min vs return ans TrapIn your original code, the final line was return min instead of return ans. This is a subtle bug. After the loop ends, min has overshot past the answer (it's now ans + 1). Always store the answer in a dedicated variable ans and return that. Using return min would return the wrong result in most cases.Common Mistakes to AvoidWrong lower bound: Setting low = min(nums) instead of low = 1 seems intuitive but is wrong. A divisor smaller than the minimum element is still valid — for example, dividing [5, 9] by 3 gives ⌈5/3⌉ + ⌈9/3⌉ = 2 + 3 = 5, which could be within threshold.Forgetting ceiling division: Using arr[i] / mid (integer division, which truncates) instead of Math.ceil((double) arr[i] / mid) is wrong. The problem explicitly states results are rounded up.Returning min instead of ans: After the binary search loop ends, min > max, meaning min has already gone past the valid answer. Always return the stored ans.Integer overflow in midpoint: Always use mid = min + (max - min) / 2 instead of (min + max) / 2. When both values are large (up to 10⁶), their sum can overflow an int.Complexity AnalysisTime Complexity: O(N × log(max(nums)))Binary search runs over [1, max(nums)] → at most log₂(10⁶) ≈ 20 iterations.Each iteration calls canDivide which is O(N).Total: O(N log M) where M = max(nums).Space Complexity: O(1) No extra data structures — only a few integer variables are used throughout.How This Relates to LeetCode 1011This problem and LeetCode 1011 (Ship Packages Within D Days) are almost identical in structure:🔗 LeetCode 1011 #Search space: [max(weights), sum(weights)]Feasibility check: Can we ship in ≤ D days?Monotonic property: More capacity → fewer daysGoal: Minimize capacityLeetCode 1283Search space: [1, max(nums)]Feasibility check: Is ceiling sum ≤ threshold?Monotonic property: Larger divisor → smaller sumGoal: Minimize divisorOnce you deeply understand one, the other takes minutes to solve.Similar Problems (Same Pattern — Binary Search on Answer)LeetCode 875 — Koko Eating Bananas [ Blog is also avaliable on this - Read Now ]LeetCode 1011 — Capacity To Ship Packages Within D Days [ Blog is also avaliable on this - Read Now ]LeetCode 410 — Split Array Largest SumLeetCode 2064 — Minimized Maximum of Products Distributed to Any StoreAll follow the same template: identify a monotonic answer space, write an O(N) feasibility check, and binary search over it.Key Takeaways✅ When the problem asks "find the minimum value such that a condition holds" — think Binary Search on the Answer.✅ The lower bound is the most constrained valid value (1 here, since divisors must be positive).✅ The upper bound is the least constrained valid value (max element, guarantees sum = length ≤ threshold).✅ Ceiling division in Java requires casting to double: Math.ceil((double) a / b).✅ Always store the answer in a separate ans variable — never return min or max directly after a binary search loop.Happy Coding! Smash that upvote if this helped you crack the pattern. 🚀

LeetCodeBinary SearchMediumJavaBinary Search on AnswerArraysCeiling Division

LeetCode 875: Koko Eating Bananas – Find the Minimum Eating Speed Using Binary Search

Try the ProblemYou can practice the problem here:https://leetcode.com/problems/koko-eating-bananas/Problem DescriptionKoko loves eating bananas 🍌.You are given n piles of bananas, where the i-th pile contains piles[i] bananas.The guards have left and will return after h hours. Koko wants to finish eating all the bananas before the guards come back.Koko can choose her banana-eating speed k bananas per hour.However, there are some important rules:Every hour, Koko chooses one pile of bananas.She eats k bananas from that pile.If the pile contains fewer than k bananas, she eats all of them and stops for that hour.She cannot move to another pile in the same hour.Your task is to determine the minimum integer value of k such that Koko can finish all the bananas within h hours.Example WalkthroughExample 1Inputpiles = [3,6,7,11]h = 8Output4Explanation:If Koko eats 4 bananas per hour, the time taken for each pile is:3 bananas → 1 hour6 bananas → 2 hours7 bananas → 2 hours11 bananas → 3 hoursTotal time required:1 + 2 + 2 + 3 = 8 hoursSince Koko finishes all bananas within 8 hours, the minimum speed is 4 bananas per hour.Example 2Inputpiles = [30,11,23,4,20]h = 5Output30Example 3Inputpiles = [30,11,23,4,20]h = 6Output23Constraints1 <= piles.length <= 10^4piles.length <= h <= 10^91 <= piles[i] <= 10^9Important observations:A pile may contain up to one billion bananas.The number of hours can also be extremely large.A naive solution may become computationally expensive.Intuition Behind the ProblemThe key observation in this problem is the relationship between eating speed and required hours.If Koko eats slowly, she needs more hours.If she eats faster, she needs fewer hours.This creates a monotonic relationship:Eating Speed ↑ → Hours Required ↓Because of this property, we can apply Binary Search on the answer.Instead of testing every possible eating speed, we can efficiently search the correct speed using binary search.Approach 1: Brute ForceIdeaTry every possible eating speed:k = 1 → max(piles)For each speed:Calculate the total hours required.If the hours are less than or equal to h, return that speed.DrawbackThe maximum pile size can be:10^9Trying all speeds up to 10^9 would take too long.Time ComplexityO(max(pile) × n)This approach is not feasible for large inputs.Approach 2: Binary Search on Answer (Optimal Solution)Since the answer lies between 1 and the maximum pile size, we can apply binary search.Search SpaceMinimum possible speed:1 banana/hourMaximum possible speed:max(piles)Binary Search StrategyChoose a middle value mid as the candidate eating speed.Calculate how many hours Koko needs at this speed.If the hours are less than or equal to h, try a smaller speed.If the hours are greater than h, increase the speed.This continues until we find the minimum valid speed.Java Implementationclass Solution { // Function to calculate total hours needed // if Koko eats bananas at a given speed public int hourCalculate(int[] piles, int speed){ int hours = 0; // Traverse through each pile for(int i = 0; i < piles.length; i++){ // Calculate hours needed for this pile // Using ceiling division hours += Math.ceil((double)piles[i] / speed); } return hours; } public int minEatingSpeed(int[] piles, int h) { // Minimum possible eating speed int low = 1; // Maximum possible speed int high = Integer.MIN_VALUE; // Find the maximum pile for(int pile : piles){ high = Math.max(high, pile); } int answer = high; // Binary Search while(low <= high){ int mid = low + (high - low) / 2; // Calculate required hours at speed mid int requiredHours = hourCalculate(piles, mid); if(requiredHours <= h){ // mid is a valid answer answer = mid; // Try smaller speed high = mid - 1; } else{ // Speed too slow low = mid + 1; } } return answer; }}Time ComplexityBinary Search runs in:O(log(max(pile)))Each iteration calculates hours in:O(n)Overall complexity:O(n log(max(pile)))Space ComplexityO(1)No extra memory is required.Key TakeawayThis problem is a classic example of Binary Search on Answer.Whenever a problem asks:“Find the minimum or maximum value such that a condition is satisfied”You should consider applying Binary Search on the answer space.ConclusionInstead of testing every possible eating speed, we used Binary Search to efficiently find the minimum speed that allows Koko to finish the bananas within the given number of hours.This approach dramatically improves performance and is a common technique used in many coding interview problems involving optimization and search space reduction.

Binary SearchBinary Search on AnswerArraysLeetCodeMediumJava