Find the Smallest Divisor

▶

Steps

setup

Initialize Search Range

Set the initial search range for the divisor from 1 to the maximum number in the array, which is 9.

💡 Starting with the full possible range ensures we don't miss any potential divisor.

Line:

low, high = 1, max(nums)

💡 The divisor must be at least 1 and at most the largest number in nums.

compare

Calculate Midpoint Divisor

Calculate mid as the integer division of (low + high) // 2, which is (1 + 9) // 2 = 5.

💡 Midpoint divides the search space to test feasibility efficiently.

Line:

mid = (low + high) // 2

💡 Mid is the current divisor candidate to check.

compare

Check Feasibility with Divisor 5

Calculate sum of ceil(nums[i]/5): ceil(1/5)=1, ceil(2/5)=1, ceil(5/5)=1, ceil(9/5)=2; total = 5 ≤ threshold 6.

💡 Feasibility check tells if divisor 5 keeps sum within threshold.

Line:

if is_feasible(nums, mid, threshold):

💡 Divisor 5 is feasible, so we can try smaller or equal divisors.

shrink

Update High to Mid

Since divisor 5 is feasible, set high = mid to narrow search space to [1,5].

💡 We keep mid because it might be the smallest feasible divisor.

Line:

high = mid

💡 Search space shrinks from the right side.

compare

Calculate Midpoint Divisor

Calculate mid as (1 + 5) // 2 = 3 to test smaller divisor candidates.

💡 Midpoint recalculation focuses the search on smaller divisors.

Line:

mid = (low + high) // 2

💡 Mid is now 3, a smaller divisor candidate.

compare

Check Feasibility with Divisor 3

Calculate sum of ceil(nums[i]/3): ceil(1/3)=1, ceil(2/3)=1, ceil(5/3)=2, ceil(9/3)=3; total = 7 > threshold 6.

💡 Divisor 3 is too small, causing sum to exceed threshold.

Line:

if is_feasible(nums, mid, threshold):

💡 Divisor 3 is not feasible, so we must try larger divisors.

expand

Update Low to Mid + 1

Since divisor 3 is not feasible, set low = mid + 1 = 4 to search larger divisors.

💡 We discard all divisors ≤ 3 because they fail feasibility.

Line:

low = mid + 1

💡 Search space shrinks from the left side.

compare

Calculate Midpoint Divisor

Calculate mid as (4 + 5) // 2 = 4 to test divisor 4.

💡 Midpoint recalculation narrows search to divisors 4 and 5.

Line:

mid = (low + high) // 2

💡 Mid is now 4, the next divisor candidate.

compare

Check Feasibility with Divisor 4

Calculate sum of ceil(nums[i]/4): ceil(1/4)=1, ceil(2/4)=1, ceil(5/4)=2, ceil(9/4)=3; total = 7 > threshold 6.

💡 Divisor 4 is still too small, sum exceeds threshold.

Line:

if is_feasible(nums, mid, threshold):

💡 Divisor 4 is not feasible, so we try larger divisors.

expand

Update Low to Mid + 1

Since divisor 4 is not feasible, set low = mid + 1 = 5 to focus on divisor 5.

💡 We discard divisor 4 and below, focusing on the last candidate.

Line:

low = mid + 1

💡 Search space is now a single element: 5.

compare

Calculate Midpoint Divisor

Calculate mid as (5 + 5) // 2 = 5, the last candidate divisor.

💡 Midpoint calculation confirms the final candidate.

Line:

mid = (low + high) // 2

💡 Mid is 5, the only divisor left to test.

compare

Check Feasibility with Divisor 5

Recalculate sum of ceil(nums[i]/5): 1 + 1 + 1 + 2 = 5 ≤ threshold 6, confirming feasibility.

💡 Final feasibility check confirms divisor 5 works.

Line:

if is_feasible(nums, mid, threshold):

💡 Divisor 5 is feasible and is the smallest divisor in the search space.

final_state

Conclude Search and Return Result

Since low equals high at 5, return 5 as the smallest divisor meeting the threshold.

💡 When low meets high, the search is complete and the answer is found.

Line:

return low

💡 The smallest divisor is 5.

import math

def is_feasible(nums, divisor, threshold):
    total = 0
    for num in nums:
        total += math.ceil(num / divisor)  # STEP 3,6,9,12
        if total > threshold:
            return False
    return True

def smallest_divisor(nums, threshold):
    low, high = 1, max(nums)  # STEP 1
    while low < high:
        mid = (low + high) // 2  # STEP 2,5,8,11
        if is_feasible(nums, mid, threshold):  # STEP 3,6,9,12
            high = mid  # STEP 4
        else:
            low = mid + 1  # STEP 7,10
    return low  # STEP 13

if __name__ == "__main__":
    nums = [1, 2, 5, 9]
    threshold = 6
    print(smallest_divisor(nums, threshold))  # Output: 5

📊

Find the Smallest Divisor - Watch the Algorithm Execute, Step by Step

Watching each step helps you understand how binary search can be applied not just on arrays but on answer spaces, a powerful technique for optimization problems.

1

0

lo

2

1

5

2

9

3

Next: lo=1 hi=9

Target: 5

1

0

lo

2

1

5

2

9

3

Next: lo=1 hi=9

Target: 5

1

0

lo

2

1

5

2

9

3

Next: lo=1 hi=5

1

0

lo

2

1

5

2

9

3

Next: lo=1 hi=5

Target: 3

1

0

lo

2

1

5

2

mid

9

3

mid[3]=3 - not evaluated yet

Next: lo=1 hi=5

Target: 3

1

0

lo

2

1

5

2

mid

9

3

mid[3]=3 - sum = 7 > threshold (not feasible)

Next: lo=4 hi=5

1

0

2

1

5

2

9

3

Next: lo=4 hi=5

Target: 4

1

0

2

1

5

2

9

3

Next: lo=4 hi=5

Target: 4

1

0

2

1

5

2

9

3

Next: lo=5 hi=5

1

0

2

1

5

2

9

3

Next: lo=5 hi=5

Target: 5

1

0

2

1

5

2

9

3

Next: lo=5 hi=5

Target: 5

1

0

2

1

5

2

9

3

Next: lo=5 hi=5

Target: 5

1

0

2

1

5

2

9

3

Next: lo=5 hi=5

Key Takeaways

✓ Binary search can be applied on the answer space, not just on sorted arrays.

This insight is hard to see from code alone because the search space is conceptual, not the input array.

✓ Feasibility checks guide how the search space shrinks from left or right.

Watching the sum comparisons visually clarifies why we move low or high pointers.

✓ The algorithm converges when low meets high, guaranteeing the smallest feasible divisor.

Seeing the pointers meet visually confirms the stopping condition and correctness.

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. Consider the following Python code that finds the k-th smallest number in an m x n multiplication table. What is the output when m = 3, n = 3, and k = 5?

easy

A. 6

B. 4

C. 3

D. 5

Solution

1. Step 1: Trace countLessEqual for mid=4

   For mid=4, count = sum of min(3, 4//i): i=1 -> min(3,4)=3; i=2 -> min(3,2)=2; i=3 -> min(3,1)=1; total=6 ≥ k=5, so high=4.

2. Step 2: Trace countLessEqual for mid=3

   For mid=3, count = i=1 -> 3; i=2 -> 1; i=3 -> 1; total=5 ≥ k=5, so high=3.

3. Step 3: Trace countLessEqual for mid=2

   For mid=2, count = i=1 -> 2; i=2 -> 1; i=3 -> 0; total=3 < k=5, so low=3.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Output matches expected k-th smallest number 5 [OK]

Hint: Count function caps counts per row [OK]

Common Mistakes:

• Off-by-one in counting
• Not breaking early in countLessEqual

3. Consider the following code snippet implementing the binary search on value range approach to find the median of two sorted arrays. Given nums1 = [1, 3] and nums2 = [2, 4], what is the final returned median?

easy

A. 2.0

B. 2.5

C. 3.0

D. 2.25

Solution

1. Step 1: Trace binary search iterations

   Initial left=1, right=4. Mid=2, countLessEqual(2)=3 ≥ 2.5 so right=2. Next mid=1, countLessEqual(1)=1 < 2.5 so left=2.

2. Step 2: Compute median for even total length

   Left=2, total length=4 (even). Candidates before 2 are nums1[0]=1 and nums2[0]=2, max=2. Median=(2+3)/2=2.5 is correct median of combined sorted array [1,2,3,4]. The code snippet's logic is incomplete but assuming correct logic, median is 2.5.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Median of combined sorted array [1,2,3,4] is 2.5 [OK]

Hint: Median of [1,2,3,4] is average of 2 and 3 [OK]

Common Mistakes:

• Off-by-one in bisect boundaries
• Confusing left with median
• Ignoring even length median averaging

4. You are given an array of non-negative integers and a number m. You want to split the array into m non-empty continuous subarrays such that the largest sum among these subarrays is minimized. Which algorithmic approach guarantees finding this minimal largest sum efficiently?

easy

A. Dynamic programming with memoization over all possible splits

B. Greedy approach that always splits when the current sum exceeds a fixed threshold

C. Binary search on the answer space combined with a greedy feasibility check

D. Sorting the array and using two pointers to find the minimal largest sum

Solution

1. Step 1: Understand the problem constraints

   The problem requires minimizing the largest sum among m subarrays, which is a classic optimization problem over a numeric answer space.

2. Step 2: Identify the approach that efficiently searches the answer space

   Binary search on the possible sums combined with a greedy check to verify feasibility is the standard approach that guarantees optimality and efficiency.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Binary search on answer space is the canonical pattern for this problem [OK]

Hint: Minimize max sum -> binary search on answer space [OK]

Common Mistakes:

• Assuming greedy splitting always yields optimal solution
• Trying DP without pruning leads to exponential time
• Sorting does not help because order matters

5. 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