Minimize a Feasible Value

Practice Exercise Interview Easy Binary Search on Answer

Checking your account…

Loading the interactive Practice workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Practice workspace

Problem

Implement minimum_square_side(item_count). Return the smallest nonnegative integer side such that side * side is at least item_count. Use the monotone feasible/infeasible boundary; item_count may be zero.

Starter code

def minimum_square_side(item_count):
    pass

Test cases

non-square

{
  "args": [
    10
  ]
}

Expected: 4

exact-square

{
  "args": [
    25
  ]
}

Expected: 5

Wizard outline

Step 1: Handle the zero answer
Return 0 when no capacity is required. Zero is the only input whose smallest feasible side is the lower bound itself without any positive search range.
Step 2: Establish the first positive boundary
Return 1 for a single item. The one-item case confirms that positive answers begin at one, not zero.
Step 3: Search an exact square boundary
Shrink integer bounds until they meet on an exact root. This checkpoint introduces the binary-search loop while deliberately exposing the strict-predicate mistake on non-squares next.
Step 4: Keep the first feasible side
Treat equality as feasible and return the converged boundary directly. For non-squares, floor square root is infeasible; the first side with side² >= item_count is the required ceiling.

Footguns and prerequisites

Testing side * side > item_count instead of >= skips exact square roots.
Starting the lower bound at one returns the wrong result for zero items.
arrays strings two pointers sliding window

Reviewed references

Python bisect — Array Bisection Algorithm

Prepared Interview Problems

Cutting Ribbons(opens in a new tab)
Minimize a Feasible Value isolates left is the first unresolved candidate and right is always a feasible candidate, so the smallest feasible value remains inside [left, right]. That focused state discipline is required when implementing cutting ribbons as a complete Interview Problem.
Koko Eating Bananas(opens in a new tab)
Minimize a Feasible Value isolates left is the first unresolved candidate and right is always a feasible candidate, so the smallest feasible value remains inside [left, right]. That focused state discipline is required when implementing koko eating bananas as a complete Interview Problem.
Ship Packages Within D Days(opens in a new tab)
Minimize a Feasible Value isolates left is the first unresolved candidate and right is always a feasible candidate, so the smallest feasible value remains inside [left, right]. That focused state discipline is required when implementing ship packages within days as a complete Interview Problem.

Recommended approach and implementation

When feasibility changes monotonically as a numeric answer grows, search the answer range instead of enumerating candidates. left is the first unresolved candidate and right is always a feasible candidate, so the smallest feasible value remains inside [left, right].

Why it works: Feasibility is monotone in the square side length. A feasible midpoint keeps the answer at or below mid; an infeasible midpoint proves every smaller candidate impossible, so convergence returns the minimum feasible side.

def minimum_square_side(item_count):
    left, right = 0, item_count
    while left < right:
        mid = (left + right) // 2
        if mid * mid >= item_count:
            right = mid
        else:
            left = mid + 1
    return left