Prepin
Log in

Assess a vessel's ability to transport packages within D days.

Approach / Explanation

This question provides the weight of each package intended for shipping and the total number of days available for the ship to transport them. Our task is to calculate the ship's capacity, specifically determining the maximum weight it can carry each day to ensure all packages are delivered within D days. Here are some important points to keep in mind while writing your code: You must calculate the ship's capacity so that all packages can be shipped within D days. The ship is not allowed to break any package into smaller pieces; each must be shipped in its entirety. It's essential to find the minimum capacity that the ship needs. This problem can be addressed using a binary search algorithm to identify the minimum ship capacity, with the search range being max(packages[i]) to sum(packages[i]) . The ship needs to carry at least the weight of the heaviest package and at most all packages in one day.

Suggested Answer

Here's a rephrased version of your content while keeping the original meaning intact: def determine_capacity ( packages , D ) : left , right = max ( packages ) , sum ( packages ) while left < right : mid = ( left + right ) // 2 if sum ( ( x - 1 ) // mid + 1 for x in packages ) > D : left = mid + 1 else : right = mid return left The example above illustrates the use of binary search to determine the ship's minimum capacity. The sum function calculates the number of days required to transport the cargo given a specific capacity. This value is then compared to D, and the binary search range is adjusted accordingly.

Alternative Answer

Here’s a rephrased version of the content: ```python def determine_capacity(packages, D): left, right = max(packages), sum(packages) while left mid: cur = 0 day += 1 cur += packages[i] if day > D: left = mid + 1 else: right = mid return left ``` In the second example, we adopt a method similar to the first, but instead of utilizing the `sum` function, we iterate over the packages, adding their weights to the current weight until it surpasses `mid`, which represents the ship's current capacity being evaluated. When it exceeds, we reset the current weight to zero and increment the day counter. We then verify if the number of days exceeds `D` to adjust the binary search range accordingly.

Question Details

Difficulty & Category

Medium
algorithms

Companies

Meta (Facebook)

Product

For CandidatesFor RecruitersCompaniesBrowse JobsInterview QuestionsDeep ProfileSkill AssessmentOpportunity Matching
Prepin.ai

© 2026 Prepin LLC · Philadelphia, PA · All rights reserved.