Minimum Speed to Arrive on Time

🎯

Minimum Speed to Arrive on Time

mediumBINARY_SEARCHAmazonGoogle

Imagine you need to catch a train and want to know the minimum speed you must drive to arrive on time given multiple road segments and a strict deadline.

💡 This problem is a classic example of binary searching over a range of possible answers rather than over array indices. Beginners often struggle because they try to binary search the input array instead of the answer space, and they may not understand how to check feasibility efficiently.

📋

Problem Statement

You are given an array 'dist' where dist[i] represents the distance of the i-th road segment you must travel. You are also given a floating point number 'hour' representing the total time you have to reach your destination. You must travel the segments in order. For each segment except the last, you must travel at an integer speed and can only depart at an integer hour (meaning you must wait until the next integer hour if you arrive early). For the last segment, you can travel at any speed and do not need to wait. Return the minimum integer speed required to reach the destination within 'hour'. If it is impossible to arrive on time, return -1.

1 ≤ dist.length ≤ 10^51 ≤ dist[i] ≤ 10^51 ≤ hour ≤ 10^7hour has at most two digits after the decimal point

💡

Example

Input"dist = [1, 3, 2], hour = 6"

Output1

At speed 1, times are [1/1=1, 3/1=3, 2/1=2], total 6 hours exactly.

Input"dist = [1, 3, 2], hour = 2.7"

Output3

At speed 3, times are [ceil(1/3)=1, ceil(3/3)=1, 2/3=0.666...], total 2.666... ≤ 2.7.

Input"dist = [1, 3, 2], hour = 1.9"

Output-1

Impossible to reach on time even at very high speeds.

• Single segment with hour exactly equal to dist[0] → output is 1
• Hour less than number of segments - 1 → output is -1 (impossible)
• Large distances with large hour → output is minimum speed close to 1
• Hour is an integer → waiting times matter for all but last segment

⚠️

Common Mistakes

Not using ceiling for all but last segment

Underestimates total time, leading to incorrect feasibility results

✅ Use math.ceil or equivalent for all but last segment time calculations

Binary searching over the input array instead of speed range

Fails to find correct speed, or leads to incorrect logic

✅ Binary search must be on the speed (answer) space, not on dist array indices

Using floating point equality checks instead of precision threshold

Infinite loop or incorrect termination in floating point binary search

✅ Use a small epsilon to terminate binary search when low and high are close enough

Not handling the last segment differently (no ceiling)

Overestimates total time, possibly returning higher speed than needed

✅ Calculate last segment time as exact division without ceiling

🧠

Brute Force (Linear Search on Speed)

💡 This approach exists to build intuition about the problem by trying every possible speed starting from 1 upwards until the time constraint is met. It is simple but inefficient, illustrating why a better method is needed.

Intuition

Try every speed from 1 upwards, calculate total travel time, and stop when the time is less than or equal to the given hour.

Algorithm

1. Initialize speed to 1.
2. Calculate total travel time at current speed.
3. If total time ≤ hour, return current speed.
4. Otherwise, increment speed and repeat.

💡 The main difficulty is understanding how to compute total time including the waiting for integer hours on all but the last segment.

</>

Code

from math import ceil

def min_speed_on_time(dist, hour):
    speed = 1
    max_speed = 10**7  # upper bound to avoid infinite loop
    while speed <= max_speed:
        total_time = 0.0
        for i in range(len(dist) - 1):
            total_time += ceil(dist[i] / speed)
        total_time += dist[-1] / speed
        if total_time <= hour:
            return speed
        speed += 1
    return -1

# Driver code
if __name__ == '__main__':
    print(min_speed_on_time([1,3,2], 6))  # Expected: 1
    print(min_speed_on_time([1,3,2], 2.7))  # Expected: 3
    print(min_speed_on_time([1,3,2], 1.9))  # Expected: -1

Line Notes

speed = 1Start checking speeds from the minimum possible speed

max_speed = 10**7Set an upper bound to prevent infinite loops

for i in range(len(dist) - 1)Calculate time for all but last segment with ceiling to account for waiting

if total_time <= hourCheck if current speed meets the time constraint to return result early

import java.util.*;

public class MinSpeedOnTime {
    public static int minSpeedOnTime(int[] dist, double hour) {
        int speed = 1;
        int maxSpeed = 10000000; // upper bound
        while (speed <= maxSpeed) {
            double totalTime = 0.0;
            for (int i = 0; i < dist.length - 1; i++) {
                totalTime += Math.ceil((double) dist[i] / speed);
            }
            totalTime += (double) dist[dist.length - 1] / speed;
            if (totalTime <= hour) {
                return speed;
            }
            speed++;
        }
        return -1;
    }

    public static void main(String[] args) {
        System.out.println(minSpeedOnTime(new int[]{1,3,2}, 6)); // 1
        System.out.println(minSpeedOnTime(new int[]{1,3,2}, 2.7)); // 3
        System.out.println(minSpeedOnTime(new int[]{1,3,2}, 1.9)); // -1
    }
}

Line Notes

int speed = 1;Initialize speed to the lowest possible value

int maxSpeed = 10000000;Define a large upper bound to avoid infinite loops

for (int i = 0; i < dist.length - 1; i++)Calculate time for all but last segment with ceiling to handle waiting

if (totalTime <= hour)Check if current speed satisfies the time constraint to return early

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

int minSpeedOnTime(vector<int>& dist, double hour) {
    int speed = 1;
    int maxSpeed = 10000000; // upper bound
    while (speed <= maxSpeed) {
        double totalTime = 0.0;
        for (int i = 0; i < (int)dist.size() - 1; i++) {
            totalTime += ceil((double)dist[i] / speed);
        }
        totalTime += (double)dist.back() / speed;
        if (totalTime <= hour) {
            return speed;
        }
        speed++;
    }
    return -1;
}

int main() {
    vector<int> dist1 = {1,3,2};
    cout << minSpeedOnTime(dist1, 6) << "\n"; // 1
    cout << minSpeedOnTime(dist1, 2.7) << "\n"; // 3
    cout << minSpeedOnTime(dist1, 1.9) << "\n"; // -1
    return 0;
}

Line Notes

int speed = 1;Start speed from the minimum possible value

int maxSpeed = 10000000;Set a large upper bound to avoid infinite loops

for (int i = 0; i < (int)dist.size() - 1; i++)Calculate time for all but last segment using ceiling to account for waiting

if (totalTime <= hour)Check if current speed meets the time constraint to return early

function minSpeedOnTime(dist, hour) {
    let speed = 1;
    const maxSpeed = 10000000; // upper bound
    while (speed <= maxSpeed) {
        let totalTime = 0;
        for (let i = 0; i < dist.length - 1; i++) {
            totalTime += Math.ceil(dist[i] / speed);
        }
        totalTime += dist[dist.length - 1] / speed;
        if (totalTime <= hour) {
            return speed;
        }
        speed++;
    }
    return -1;
}

// Test cases
console.log(minSpeedOnTime([1,3,2], 6)); // 1
console.log(minSpeedOnTime([1,3,2], 2.7)); // 3
console.log(minSpeedOnTime([1,3,2], 1.9)); // -1

Line Notes

let speed = 1;Initialize speed to the smallest possible value

const maxSpeed = 10000000;Define an upper bound to prevent infinite loops

for (let i = 0; i < dist.length - 1; i++)Calculate time for all but last segment with ceiling to handle waiting

if (totalTime <= hour)Check if current speed satisfies the time constraint to return early

⏱

Complexity

TimeO(maxSpeed * n)

SpaceO(1)

For each speed from 1 to maxSpeed (up to 10^7), we compute total time over n segments, leading to a very large time complexity.

💡 For n=10^5 and maxSpeed=10^7, this means 10^12 operations, which is infeasible.

Interview Verdict: TLE

This approach is too slow for large inputs but helps understand the problem and correctness before optimizing.

🧠

Binary Search on Speed (Answer Space)

💡 This approach uses binary search on the range of possible speeds to efficiently find the minimum speed that meets the time constraint. It introduces the concept of a feasibility function to check if a given speed is sufficient.

Intuition

Instead of checking every speed, use binary search between 1 and a large upper bound. For each mid speed, check if arrival time ≤ hour. Narrow the search space accordingly.

Algorithm

1. Set low = 1 and high = 10^7 (upper bound).
2. While low ≤ high:
3. Calculate mid = (low + high) // 2.
4. Check if speed = mid can get you there on time using feasibility function.
5. If yes, update answer and move high to mid - 1.
6. Else, move low to mid + 1.
7. Return answer or -1 if no speed is feasible.

💡 The key is the feasibility check that simulates travel time at a given speed, including waiting times.

</>

Code

from math import ceil

def can_arrive(dist, hour, speed):
    total_time = 0.0
    for i in range(len(dist) - 1):
        total_time += ceil(dist[i] / speed)
    total_time += dist[-1] / speed
    return total_time <= hour

def min_speed_on_time(dist, hour):
    low, high = 1, 10**7
    answer = -1
    while low <= high:
        mid = (low + high) // 2
        if can_arrive(dist, hour, mid):
            answer = mid
            high = mid - 1
        else:
            low = mid + 1
    return answer

# Driver code
if __name__ == '__main__':
    print(min_speed_on_time([1,3,2], 6))  # Expected: 1
    print(min_speed_on_time([1,3,2], 2.7))  # Expected: 3
    print(min_speed_on_time([1,3,2], 1.9))  # Expected: -1

Line Notes

def can_arrive(dist, hour, speed):Defines feasibility function to check if speed meets time constraint

for i in range(len(dist) - 1):Calculate time for all but last segment with ceiling to handle waiting

total_time += dist[-1] / speedAdd exact time for last segment without waiting

if can_arrive(dist, hour, mid):Check feasibility at mid speed to adjust binary search bounds

import java.util.*;

public class MinSpeedOnTime {
    private static boolean canArrive(int[] dist, double hour, int speed) {
        double totalTime = 0.0;
        for (int i = 0; i < dist.length - 1; i++) {
            totalTime += Math.ceil((double) dist[i] / speed);
        }
        totalTime += (double) dist[dist.length - 1] / speed;
        return totalTime <= hour;
    }

    public static int minSpeedOnTime(int[] dist, double hour) {
        int low = 1, high = 10000000;
        int answer = -1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (canArrive(dist, hour, mid)) {
                answer = mid;
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return answer;
    }

    public static void main(String[] args) {
        System.out.println(minSpeedOnTime(new int[]{1,3,2}, 6)); // 1
        System.out.println(minSpeedOnTime(new int[]{1,3,2}, 2.7)); // 3
        System.out.println(minSpeedOnTime(new int[]{1,3,2}, 1.9)); // -1
    }
}

Line Notes

private static boolean canArrive(int[] dist, double hour, int speed)Feasibility function to check if speed is sufficient

for (int i = 0; i < dist.length - 1; i++)Calculate time for all but last segment with ceiling to handle waiting

totalTime += (double) dist[dist.length - 1] / speed;Add exact time for last segment without waiting

if (canArrive(dist, hour, mid))Use feasibility to adjust binary search bounds

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

bool canArrive(const vector<int>& dist, double hour, int speed) {
    double totalTime = 0.0;
    for (int i = 0; i < (int)dist.size() - 1; i++) {
        totalTime += ceil((double)dist[i] / speed);
    }
    totalTime += (double)dist.back() / speed;
    return totalTime <= hour;
}

int minSpeedOnTime(vector<int>& dist, double hour) {
    int low = 1, high = 10000000;
    int answer = -1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (canArrive(dist, hour, mid)) {
            answer = mid;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return answer;
}

int main() {
    vector<int> dist1 = {1,3,2};
    cout << minSpeedOnTime(dist1, 6) << "\n"; // 1
    cout << minSpeedOnTime(dist1, 2.7) << "\n"; // 3
    cout << minSpeedOnTime(dist1, 1.9) << "\n"; // -1
    return 0;
}

Line Notes

bool canArrive(const vector<int>& dist, double hour, int speed)Feasibility function to check if speed suffices

for (int i = 0; i < (int)dist.size() - 1; i++)Calculate time for all but last segment with ceiling to handle waiting

totalTime += (double)dist.back() / speed;Add exact time for last segment without waiting

if (canArrive(dist, hour, mid))Adjust binary search bounds based on feasibility

function canArrive(dist, hour, speed) {
    let totalTime = 0;
    for (let i = 0; i < dist.length - 1; i++) {
        totalTime += Math.ceil(dist[i] / speed);
    }
    totalTime += dist[dist.length - 1] / speed;
    return totalTime <= hour;
}

function minSpeedOnTime(dist, hour) {
    let low = 1, high = 10000000;
    let answer = -1;
    while (low <= high) {
        let mid = Math.floor((low + high) / 2);
        if (canArrive(dist, hour, mid)) {
            answer = mid;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return answer;
}

// Test cases
console.log(minSpeedOnTime([1,3,2], 6)); // 1
console.log(minSpeedOnTime([1,3,2], 2.7)); // 3
console.log(minSpeedOnTime([1,3,2], 1.9)); // -1

Line Notes

function canArrive(dist, hour, speed)Feasibility function to check if speed meets time constraint

for (let i = 0; i < dist.length - 1; i++)Calculate time for all but last segment with ceiling to handle waiting

totalTime += dist[dist.length - 1] / speed;Add exact time for last segment without waiting

if (canArrive(dist, hour, mid))Adjust binary search bounds based on feasibility

⏱

Complexity

TimeO(n log(maxSpeed))

SpaceO(1)

Binary search runs in log(maxSpeed) iterations, each checking n segments for feasibility.

💡 For n=10^5 and maxSpeed=10^7, this means about 24 * 10^5 = 2.4 million operations, which is efficient enough.

Interview Verdict: Accepted

This approach is efficient and practical for large inputs, making it the preferred solution in interviews.

🧠

Binary Search with Floating Point Precision

💡 This approach refines the binary search by searching over floating point speeds with a precision threshold, useful if the problem allowed non-integer speeds. It demonstrates handling floating point comparisons and precision control.

Intuition

Instead of integer speeds, binary search over a floating point range with a small epsilon to find minimum speed with required precision.

Algorithm

1. Set low = 1.0 and high = 10^7.0.
2. While high - low > epsilon (e.g., 1e-6):
3. mid = (low + high) / 2.
4. Check feasibility at mid speed.
5. If feasible, set high = mid.
6. Else, set low = mid.
7. Return ceil(high) as minimum integer speed.

💡 The key is controlling precision and converting the final floating point speed to an integer.

</>

Code

from math import ceil

def can_arrive(dist, hour, speed):
    total_time = 0.0
    for i in range(len(dist) - 1):
        total_time += ceil(dist[i] / speed)
    total_time += dist[-1] / speed
    return total_time <= hour

def min_speed_on_time(dist, hour):
    low, high = 1.0, 10**7
    epsilon = 1e-6
    while high - low > epsilon:
        mid = (low + high) / 2
        if can_arrive(dist, hour, mid):
            high = mid
        else:
            low = mid
    return ceil(high)

# Driver code
if __name__ == '__main__':
    print(min_speed_on_time([1,3,2], 6))  # Expected: 1
    print(min_speed_on_time([1,3,2], 2.7))  # Expected: 3
    print(min_speed_on_time([1,3,2], 1.9))  # Expected: -1 (handled by ceil)

Line Notes

low, high = 1.0, 10**7Initialize floating point search bounds

epsilon = 1e-6Set precision threshold for binary search termination

while high - low > epsilon:Loop until desired precision is reached

return ceil(high)Return smallest integer speed greater or equal to high

import java.util.*;

public class MinSpeedOnTime {
    private static boolean canArrive(int[] dist, double hour, double speed) {
        double totalTime = 0.0;
        for (int i = 0; i < dist.length - 1; i++) {
            totalTime += Math.ceil(dist[i] / speed);
        }
        totalTime += dist[dist.length - 1] / speed;
        return totalTime <= hour;
    }

    public static int minSpeedOnTime(int[] dist, double hour) {
        double low = 1.0, high = 10000000.0;
        double epsilon = 1e-6;
        while (high - low > epsilon) {
            double mid = (low + high) / 2.0;
            if (canArrive(dist, hour, mid)) {
                high = mid;
            } else {
                low = mid;
            }
        }
        return (int) Math.ceil(high);
    }

    public static void main(String[] args) {
        System.out.println(minSpeedOnTime(new int[]{1,3,2}, 6)); // 1
        System.out.println(minSpeedOnTime(new int[]{1,3,2}, 2.7)); // 3
        System.out.println(minSpeedOnTime(new int[]{1,3,2}, 1.9)); // -1 (ceil handles)
    }
}

Line Notes

double low = 1.0, high = 10000000.0;Initialize floating point bounds

double epsilon = 1e-6;Precision threshold for binary search

while (high - low > epsilon)Loop until precision is sufficient

return (int) Math.ceil(high);Return minimum integer speed after floating point search

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

bool canArrive(const vector<int>& dist, double hour, double speed) {
    double totalTime = 0.0;
    for (int i = 0; i < (int)dist.size() - 1; i++) {
        totalTime += ceil(dist[i] / speed);
    }
    totalTime += dist.back() / speed;
    return totalTime <= hour;
}

int minSpeedOnTime(vector<int>& dist, double hour) {
    double low = 1.0, high = 10000000.0;
    double epsilon = 1e-6;
    while (high - low > epsilon) {
        double mid = (low + high) / 2.0;
        if (canArrive(dist, hour, mid)) {
            high = mid;
        } else {
            low = mid;
        }
    }
    return (int)ceil(high);
}

int main() {
    vector<int> dist1 = {1,3,2};
    cout << minSpeedOnTime(dist1, 6) << "\n"; // 1
    cout << minSpeedOnTime(dist1, 2.7) << "\n"; // 3
    cout << minSpeedOnTime(dist1, 1.9) << "\n"; // -1 (ceil handles)
    return 0;
}

Line Notes

double low = 1.0, high = 10000000.0;Initialize floating point search bounds

double epsilon = 1e-6;Set precision threshold

while (high - low > epsilon)Loop until precision is reached

return (int)ceil(high);Return minimum integer speed after floating point binary search

function canArrive(dist, hour, speed) {
    let totalTime = 0;
    for (let i = 0; i < dist.length - 1; i++) {
        totalTime += Math.ceil(dist[i] / speed);
    }
    totalTime += dist[dist.length - 1] / speed;
    return totalTime <= hour;
}

function minSpeedOnTime(dist, hour) {
    let low = 1.0, high = 10000000.0;
    const epsilon = 1e-6;
    while (high - low > epsilon) {
        let mid = (low + high) / 2;
        if (canArrive(dist, hour, mid)) {
            high = mid;
        } else {
            low = mid;
        }
    }
    return Math.ceil(high);
}

// Test cases
console.log(minSpeedOnTime([1,3,2], 6)); // 1
console.log(minSpeedOnTime([1,3,2], 2.7)); // 3
console.log(minSpeedOnTime([1,3,2], 1.9)); // -1 (ceil handles)

Line Notes

let low = 1.0, high = 10000000.0;Initialize floating point bounds

const epsilon = 1e-6;Precision threshold for binary search

while (high - low > epsilon)Loop until precision is sufficient

return Math.ceil(high);Return minimum integer speed after floating point search

⏱

Complexity

TimeO(n log((maxSpeed - minSpeed)/epsilon))

SpaceO(1)

Binary search with floating precision requires more iterations but still logarithmic in precision steps, each checking n segments.

💡 For epsilon=1e-6, about 20-30 iterations are needed, which is efficient for large n.

Interview Verdict: Accepted

This approach is useful when precision matters or non-integer speeds are allowed, demonstrating mastery of floating point binary search.

📊

All Approaches - One-Glance Tradeoffs

💡 In 95% of interviews, you should implement the binary search on answer space approach as it balances clarity and efficiency.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(maxSpeed * n)	O(1)	No	N/A	Mention only - never code due to inefficiency
2. Binary Search on Speed (Integer)	O(n log(maxSpeed))	O(1)	No	N/A	Code this approach for optimal solution
3. Binary Search with Floating Point Precision	O(n log((maxSpeed - minSpeed)/epsilon))	O(1)	No	N/A	Mention if asked about precision or non-integer speeds

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice the brute force approach to build intuition, then master the binary search on answer space for efficiency. Follow the step-by-step presentation to impress interviewers.

How to Present

Step 1: Clarify the problem constraints and the meaning of waiting times.Step 2: Present the brute force approach to show understanding.Step 3: Explain the inefficiency and introduce binary search on the answer space.Step 4: Implement the feasibility function and binary search.Step 5: Discuss edge cases and test your code thoroughly.

Time Allocation

Clarify: 3min → Approach: 5min → Code: 10min → Test: 7min. Total ~25min

What the Interviewer Tests

The interviewer tests your ability to recognize binary search on answer space, implement a correct feasibility function, handle floating point arithmetic, and optimize for large inputs.

Common Follow-ups

• What if speeds can be floating point numbers? → Use floating point binary search with precision.
• How to handle very large inputs efficiently? → Use binary search with O(n log maxSpeed) complexity.

💡 These follow-ups test your understanding of precision and scalability, common in real-world scenarios.

🔍

Pattern Recognition

When to Use

1) Problem asks for minimum/maximum value satisfying a condition; 2) Condition can be checked efficiently; 3) Input size too large for brute force; 4) Problem involves monotonicity in answer space.

Signature Phrases

'minimum speed to arrive on time''can you reach within hour?''find smallest/largest value satisfying condition'

NOT This Pattern When

Problems that require binary search on sorted arrays or classic binary search on indices rather than answer space.

Similar Problems

Koko Eating Bananas - minimum eating speed to finish piles in timeCapacity To Ship Packages Within D Days - minimum capacity to ship packages on timeSplit Array Largest Sum - minimize largest subarray sum to split array

Practice

1. Consider the following Python code implementing the optimal approach to find k closest elements to x in a sorted array. What is the returned output when calling findClosestElements([1, 3, 5], 2, 4)?

easy

A. [1, 3]

B. [3, 4]

C. [1, 5]

D. [3, 5]

Solution

1. Step 1: Initialize variables

   Array length is 3, k=2, so low=0, high=1.

2. Step 2: First iteration of binary search

   Calculate mid = (0+1)//2 = 0. Compare x - arr[mid] = 4 - 1 = 3 and arr[mid + k] - x = arr[2] - 4 = 5 - 4 = 1. Since 3 > 1, set low = mid + 1 = 1.

3. Step 3: Loop ends as low == high == 1

   Return arr[1:3] = [3, 5].

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Binary search correctly chooses window starting at index 1 [OK]

Hint: Check mid and window edges distances carefully [OK]

Common Mistakes:

• Off-by-one error in slicing window
• Incorrect comparison direction in if condition
• Returning wrong slice boundaries

2. Examine the following buggy code snippet for finding the smallest divisor. Which line contains the subtle bug that can cause incorrect results on some inputs?

medium

A. Line with total += num // divisor

B. Line with if total > threshold:

C. Line with mid = (low + high) // 2

D. Line with low, high = 1, max(nums)

Solution

1. Step 1: Identify the purpose of is_feasible

   It sums the ceiling division of each num by divisor to check if total ≤ threshold.

2. Step 2: Spot the bug in division

   Using integer division (//) underestimates the sum because it truncates instead of rounding up.

3. Step 3: Consequence of the bug

   Underestimating sum may cause the function to incorrectly return True, leading to wrong smallest divisor.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Ceiling division needed, integer division breaks correctness -> [OK]

Hint: Ceiling division needed, integer division underestimates sum [OK]

Common Mistakes:

• Using integer division instead of ceiling
• Incorrect binary search boundaries
• Not early exiting feasibility check

3. The following code attempts to compute the integer square root using Newton's method. Which line contains a subtle bug that can cause incorrect results or infinite loops for inputs 0 or 1?

medium

A. Line 1: def mySqrt(x: int) -> int:

B. Line 2: guess = x // 2

C. Line 3: while guess * guess > x:

D. Line 4: guess = (guess + x // guess) // 2

Solution

1. Step 1: Identify missing base case handling

   The code does not handle x=0 or x=1 explicitly, which can cause guess to be 0 and lead to division by zero or infinite loop.

2. Step 2: Pinpoint the bug line

   Line 2 initializes guess = x // 2 without checking if x < 2, causing issues for small inputs.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Proper base case handling prevents infinite loops [OK]

Hint: Always handle small inputs before iterative methods [OK]

Common Mistakes:

• Ignoring base cases
• Assuming guess initialization always valid
• Misplacing loop condition

4. Suppose the array can contain duplicate elements and you want to find the first position where the target can be inserted (i.e., the leftmost insertion point). Which modification to the binary search algorithm correctly achieves this?

hard

A. When nums[mid] >= target, recurse on the left half; else recurse on the right half.

B. Change the base case to return right instead of left when left > right.

C. When nums[mid] > target, recurse on the right half; else recurse on the left half.

D. Use linear scan after binary search to find the first occurrence.

Solution

1. Step 1: Understand requirement for leftmost insertion

   We must find the earliest index where target can be inserted, including duplicates.

2. Step 2: Modify binary search condition

   If nums[mid] >= target, recurse left to find earlier occurrence; else recurse right.

3. Step 3: Avoid linear scan for efficiency

   Linear scan after binary search defeats O(log n) goal.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Condition ensures leftmost insertion index found efficiently [OK]

Hint: For leftmost insert, recurse left on >= target [OK]

Common Mistakes:

• Recursing right on >= target misses leftmost index
• Returning right instead of left at base case
• Using linear scan after binary search

5. Suppose the problem is modified so that the array is sorted but the single element can appear multiple times (not necessarily once), and all other elements appear exactly twice. Which modification to the binary search approach correctly finds the single element?

hard

A. Modify binary search to compare mid with neighbors and adjust search space based on counts of duplicates around mid

B. Switch to linear scan because binary search parity logic breaks when single element repeats

C. Use the same parity-based binary search since duplicates still appear in pairs

D. Use a hash map to count occurrences since binary search can't handle multiple single elements

Solution

1. Step 1: Understand problem change

   The single element may appear multiple times, breaking the strict pair pattern.

2. Step 2: Analyze binary search adaptation

   Parity-based halving fails; instead, compare mid with neighbors and count duplicates to decide which half to search.

3. Step 3: Confirm other options

   Linear scan is inefficient; hash map uses extra space and is unnecessary if modified binary search works.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Counting duplicates around mid guides correct binary search [OK]

Hint: Modify binary search to handle variable duplicate counts [OK]

Common Mistakes:

• Assuming parity logic still works
• Switching to linear scan prematurely
• Using extra space unnecessarily