LeetCopilot Logo
LeetCopilot
LeetCode Pattern/Binary Search/3 Feasibility Function Mistakes That Break Binary Search on Answer

3 Feasibility Function Mistakes That Break Binary Search on Answer

LeetCopilot Team
Dec 30, 2025
7 min read
Binary SearchFeasibility FunctionDebuggingCommon MistakesBinary Search on Answer
Learn the three most common mistakes in feasibility functions: wrong monotonicity direction, off-by-one in counting, and incorrect greedy logic. Get debugging tips and fixes.
Complete Guide

The Complete Binary Search Guide: Master All Patterns, Templates, and Techniques

The ultimate comprehensive guide to binary search. Learn all variants (classic, binary search on answer, rotated arrays), when to use each pattern, complete templates in multiple languages, and a systematic approach to solve any binary search problem.

Read the complete guide

Your binary search on answer returns wrong answers. The binary search logic is correct, but the feasibility function has a subtle bug.

Feasibility functions are where most mistakes happen in binary search on answer problems. This guide covers the 3 most common mistakes, how to debug them, and how to verify correctness.

TL;DR

The 3 mistakes:

  1. Wrong monotonicity direction — Checking if we can do better than mid, not if mid works
  2. Off-by-one in counting — Using pile // speed instead of ceiling division
  3. Incorrect greedy logic — Forgetting to update state in greedy placement

Quick fix checklist:

  • Does feasibility check if mid works (not if we can beat mid)?
  • Using ceiling division for "hours needed"?
  • Updating all state variables in greedy loops?

Mistake 1: Wrong Monotonicity Direction

The Problem

Checking if we can do better than mid, instead of checking if mid works.

❌ Wrong:

python
def can_finish(speed):
    hours = sum((pile + speed - 1) // speed for pile in piles)
    return hours < h  # WRONG: should be <=

Why it's wrong: We want to know if speed works, not if we can beat it.

✅ Correct:

python
def can_finish(speed):
    hours = sum((pile + speed - 1) // speed for pile in piles)
    return hours <= h  # Correct: speed works if hours <= h

Example

code
Piles: [3, 6, 7, 11], h = 8

Speed 4:
  Hours = ceil(3/4) + ceil(6/4) + ceil(7/4) + ceil(11/4)
        = 1 + 2 + 2 + 3 = 8

Wrong check: hours < h → 8 < 8 → False (says speed 4 doesn't work!)
Correct check: hours <= h → 8 <= 8 → True (speed 4 works)

How to Fix

Ask: "Does mid satisfy the constraint?"

  • Not: "Can we do better than mid?"
  • Yes: "Does mid work?"

Common patterns:

  • hours <= h (not < h)
  • days <= d (not < d)
  • subarrays <= m (not < m)

Mistake 2: Off-by-One in Counting

The Problem

Using floor division when you need ceiling division.

❌ Wrong:

python
def can_finish(speed):
    hours = sum(pile // speed for pile in piles)  # WRONG
    return hours <= h

Why it's wrong: pile // speed rounds down, but we need to round up (Koko needs a full hour even for partial pile).

✅ Correct:

python
def can_finish(speed):
    hours = sum((pile + speed - 1) // speed for pile in piles)  # Ceiling
    return hours <= h

Example

code
Pile: 7 bananas, Speed: 4 bananas/hour

Wrong: 7 // 4 = 1 hour (but Koko can only eat 4 in 1 hour!)
Correct: (7 + 4 - 1) // 4 = 10 // 4 = 2 hours (needs 2 hours for 7 bananas)

Verification: Hour 1: eat 4, Hour 2: eat 3 ✓

Ceiling Division Formulas

Python:

python
import math
hours = math.ceil(pile / speed)  # Method 1
hours = (pile + speed - 1) // speed  # Method 2 (no import)
hours = -(-pile // speed)  # Method 3 (clever trick)

JavaScript:

javascript
const hours = Math.ceil(pile / speed);

Java:

java
int hours = (pile + speed - 1) / speed;

Mistake 3: Incorrect Greedy Logic

The Problem

Forgetting to update state variables in greedy algorithms.

❌ Wrong:

python
def can_place(min_dist):
    count = 1
    last_pos = position[0]
    
    for pos in position[1:]:
        if pos - last_pos >= min_dist:
            count += 1
            # WRONG: forgot to update last_pos!
    
    return count >= m

Why it's wrong: We count the ball but don't update last_pos, so all future distances are measured from the first ball.

✅ Correct:

python
def can_place(min_dist):
    count = 1
    last_pos = position[0]
    
    for pos in position[1:]:
        if pos - last_pos >= min_dist:
            count += 1
            last_pos = pos  # Update position!
    
    return count >= m

Example

code
Positions: [1, 2, 4, 8, 9], m = 3, min_dist = 3

Wrong logic (no update):
  last_pos = 1
  pos = 2: 2 - 1 = 1 < 3 → skip
  pos = 4: 4 - 1 = 3 >= 3 → count = 2 (but last_pos still 1!)
  pos = 8: 8 - 1 = 7 >= 3 → count = 3 (but last_pos still 1!)
  pos = 9: 9 - 1 = 8 >= 3 → count = 4
  Returns True (WRONG: we placed balls at 1, 4, 8, 9 but distances are wrong!)

Correct logic (with update):
  last_pos = 1
  pos = 2: 2 - 1 = 1 < 3 → skip
  pos = 4: 4 - 1 = 3 >= 3 → count = 2, last_pos = 4
  pos = 8: 8 - 4 = 4 >= 3 → count = 3, last_pos = 8
  Returns True (Correct: balls at 1, 4, 8 with distances 3, 4)

Common Greedy State Updates

Ship packages:

python
if current_load + weight > capacity:
    days += 1
    current_load = weight  # Update load!
else:
    current_load += weight

Split array:

python
if current_sum + num > max_sum:
    subarrays += 1
    current_sum = num  # Update sum!
else:
    current_sum += num

Place balls:

python
if pos - last_pos >= min_dist:
    count += 1
    last_pos = pos  # Update position!

Debugging Checklist

When your feasibility function returns wrong results:

Step 1: Verify Monotonicity (30 seconds)

Test manually:

python
# If mid = 5 works, does mid = 6 work?
print(is_feasible(5))  # True
print(is_feasible(6))  # Should be True for minimize maximum

# If not, your feasibility function is wrong

Step 2: Check Boundary Conditions (30 seconds)

python
# Does the minimum answer work?
print(is_feasible(min_answer))  # Should be False or True depending on problem

# Does the maximum answer work?
print(is_feasible(max_answer))  # Should be True for minimize maximum

Step 3: Trace Through Example (60 seconds)

python
def can_finish(speed):
    hours = 0
    for pile in piles:
        h = (pile + speed - 1) // speed
        print(f"Pile {pile}, speed {speed}: {h} hours")
        hours += h
    print(f"Total: {hours} hours, limit: {h}")
    return hours <= h

# Trace through to find the bug
can_finish(4)

Step 4: Common Mistakes Checklist

  • Using < instead of <= (or vice versa)?
  • Using floor division instead of ceiling?
  • Forgetting to update state in greedy loop?
  • Off-by-one in loop bounds?
  • Initializing counters incorrectly?

Practice Problems

Debug these feasibility functions:

Problem 1: Koko Eating Bananas

python
# Find the bug
def can_finish(speed):
    hours = sum(pile // speed for pile in piles)  # Bug!
    return hours <= h

Problem 2: Ship Packages

python
# Find the bug
def can_ship(capacity):
    days = 1
    current_load = 0
    for weight in weights:
        if current_load + weight > capacity:
            days += 1
            # Bug: forgot to update current_load!
        else:
            current_load += weight
    return days <= max_days

Problem 3: Magnetic Force

python
# Find the bug
def can_place(min_dist):
    count = 1
    last_pos = position[0]
    for pos in position[1:]:
        if pos - last_pos > min_dist:  # Bug: should be >=
            count += 1
            last_pos = pos
    return count >= m

FAQ

Q: How do I know if I need ceiling or floor division?

A: Ask: "If I have a partial unit, do I need a full time slot?" If yes, use ceiling.

Q: My feasibility function is slow. Is that ok?

A: Yes! Feasibility can be O(n) or even O(n²). Total complexity is O(log(max-min) × feasibility_cost).

Q: Should I optimize the feasibility function?

A: Only if it's a bottleneck. Correctness first, then optimize.

Q: How do I verify my feasibility function is correct?

A: Test edge cases: min_answer, max_answer, and boundary values.

Conclusion

Feasibility functions are where most binary search on answer bugs hide. The three common mistakes:

  1. Wrong monotonicity: Using < instead of <=
  2. Off-by-one counting: Using floor instead of ceiling division
  3. Greedy state: Forgetting to update variables

Debugging strategy:

  1. Verify monotonicity
  2. Check boundary conditions
  3. Trace through examples
  4. Use the checklist

Prevention:

  • Always ask: "Does mid work?" not "Can we beat mid?"
  • Use ceiling division for "time needed" calculations
  • Update all state variables in greedy loops

Master these patterns and you'll write correct feasibility functions every time. For more details, see Binary Search on Answer and Minimize Maximum vs Maximize Minimum.

Want to Practice LeetCode Smarter?

LeetCopilot is a free browser extension that enhances your LeetCode practice with AI-powered hints, personalized study notes, and realistic mock interviews — all designed to accelerate your coding interview preparation.

Learn More About LeetCopilot
ChromeAdd to Chrome for free

Also compatible with Edge, Brave, and Opera

Related Tutorials