Kth Smallest Number in Multiplication Table

▶

Steps

setup

Initialize search boundaries

Set the initial search range from 1 to m*n (1 to 9). This range covers all possible values in the multiplication table.

💡 Starting with the full range ensures we consider all possible values for the kth smallest number.

Line:

low, high = 1, m * n

💡 The entire multiplication table's value range is from 1 to m*n, so the answer must lie within this range.

compare

Calculate mid = (low + high) // 2

Compute mid as (1 + 9) // 2 = 5. This mid value is the candidate number to test how many table entries are ≤ 5.

💡 Midpoint divides the search space to test if kth smallest is ≤ mid or greater.

Line:

mid = (low + high) // 2

💡 Mid is the pivot value for counting how many numbers are ≤ mid in the table.

compare

Count numbers ≤ mid (5) in row 1

Count how many numbers in row 1 (1*1 to 1*3) are ≤ 5. Count is min(3, 5//1) = 3.

💡 Counting per row uses integer division to find how many elements are ≤ mid efficiently.

Line:

count += min(n, mid // i)  # i=1

💡 Row 1 contributes 3 numbers ≤ 5: 1, 2, 3.

compare

Count numbers ≤ mid (5) in row 2

Count how many numbers in row 2 (2*1 to 2*3) are ≤ 5. Count is min(3, 5//2) = 2. Total count now 3 + 2 = 5.

💡 Adding counts row by row accumulates total numbers ≤ mid.

Line:

count += min(n, mid // i)  # i=2

💡 Row 2 contributes 2 numbers ≤ 5: 2, 4.

compare

Early break in counting at row 2

Since count (5) ≥ k (5), break early without counting row 3 to save time.

💡 Early break optimization avoids unnecessary counting once count ≥ k.

Line:

if count >= k:
    break

💡 We know at least k numbers are ≤ mid, so mid might be the answer or higher than needed.

shrink

Compare count with k and update high

Since count (5) ≥ k (5), set high = mid = 5 to narrow search to [1,5].

💡 If count ≥ k, the kth smallest is ≤ mid, so we shrink the upper bound.

Line:

if countLessEqual(mid) >= k:
    high = mid

💡 Search space shrinks from [1,9] to [1,5].

compare

Calculate new mid = (low + high) // 2

Compute mid as (1 + 5) // 2 = 3. Next candidate to test is 3.

💡 Mid recalculation focuses on the smaller search space.

Line:

mid = (low + high) // 2

💡 Mid is now 3, a smaller candidate to test.

compare

Count numbers ≤ mid (3) in row 1

Count numbers ≤ 3 in row 1: min(3, 3//1) = 3. Count = 3.

💡 Counting starts fresh for new mid value.

Line:

count += min(n, mid // i)  # i=1

💡 Row 1 contributes 3 numbers ≤ 3.

compare

Count numbers ≤ mid (3) in row 2

Count numbers ≤ 3 in row 2: min(3, 3//2) = 1. Total count = 3 + 1 = 4.

💡 Counting accumulates across rows.

Line:

count += min(n, mid // i)  # i=2

💡 Row 2 contributes 1 number ≤ 3.

compare

Count numbers ≤ mid (3) in row 3

Count numbers ≤ 3 in row 3: min(3, 3//3) = 1. Total count = 4 + 1 = 5.

💡 Final row count completes total count for mid.

Line:

count += min(n, mid // i)  # i=3

💡 Row 3 contributes 1 number ≤ 3.

shrink

Update high to mid since count ≥ k

Since count (5) ≥ k (5), set high = mid = 3 to narrow search to [1,3].

💡 We continue shrinking the upper bound to find the smallest number with count ≥ k.

Line:

if countLessEqual(mid) >= k:
    high = mid

💡 Search space shrinks from [1,5] to [1,3].

compare

Calculate mid = (low + high) // 2 with lo=1, hi=3

Compute mid as (1 + 3) // 2 = 2. Next candidate to test is 2.

💡 Mid recalculation focuses on the smaller search space.

Line:

mid = (low + high) // 2

💡 Mid is now 2, a smaller candidate to test.

compare

Count numbers ≤ mid (2) in row 1

Count numbers ≤ 2 in row 1: min(3, 2//1) = 2. Count = 2.

💡 Counting starts fresh for new mid value.

Line:

count += min(n, mid // i)  # i=1

💡 Row 1 contributes 2 numbers ≤ 2.

compare

Count numbers ≤ mid (2) in row 2

Count numbers ≤ 2 in row 2: min(3, 2//2) = 1. Total count = 2 + 1 = 3.

💡 Counting accumulates across rows.

Line:

count += min(n, mid // i)  # i=2

💡 Row 2 contributes 1 number ≤ 2.

compare

Count numbers ≤ mid (2) in row 3

Count numbers ≤ 2 in row 3: min(3, 2//3) = 0. Total count remains 3.

💡 Row 3 contributes no numbers ≤ 2.

Line:

count += min(n, mid // i)  # i=3

💡 Total count for mid=2 is 3, less than k=5.

expand

Update low to mid + 1 since count < k

Since count (3) < k (5), set low = mid + 1 = 3 to narrow search to [3,3].

💡 If count < k, kth smallest is greater than mid, so we raise the lower bound.

Line:

if countLessEqual(mid) < k:
    low = mid + 1

💡 Search space shrinks from [1,3] to [3,3].

reconstruct

Search complete, return low as answer

Since low equals high (3), the search ends. Return low = 3 as the kth smallest number.

💡 When lo meets hi, the smallest number with count ≥ k is found.

Line:

return low

💡 The 5th smallest number in the multiplication table is 3.

def findKthNumber(m, n, k):
    def countLessEqual(x):
        count = 0
        for i in range(1, m+1):
            count += min(n, x // i)  # STEP counting row i
            if count >= k:  # STEP early break if count >= k
                break
        return count

    low, high = 1, m * n  # STEP initialize search boundaries
    while low < high:
        mid = (low + high) // 2  # STEP calculate mid
        if countLessEqual(mid) < k:  # STEP compare count with k
            low = mid + 1  # STEP update low if count < k
        else:
            high = mid  # STEP update high if count >= k
    return low  # STEP return answer

if __name__ == '__main__':
    print(findKthNumber(3, 3, 5))  # Output: 3

📊

Kth Smallest Number in Multiplication Table - Watch the Algorithm Execute, Step by Step

Watching each step of the binary search and the counting process reveals how the algorithm efficiently finds the kth smallest number without enumerating the entire table.

Target: 5

1

0

lo

2

1

2

2

3

3

3

4

4

5

6

6

6

7

9

8

Next: lo=1 hi=9

Target: 5

1

0

lo

2

1

2

2

3

3

3

4

mid

4

5

6

6

6

7

9

8

mid[5]=5

Next: lo=1 hi=9

Target: 5

1

0

lo

2

1

2

2

3

3

3

4

mid

4

5

6

6

6

7

9

8

mid[5]=5 - count after row 1: 3

Next: lo=1 hi=9

Target: 5

1

0

lo

2

1

2

2

3

3

3

4

mid

4

5

6

6

6

7

9

8

mid[5]=5 - count after row 2: 5

Next: lo=1 hi=9

Target: 5

1

0

lo

2

1

2

2

3

3

3

4

mid

4

5

6

6

6

7

9

8

mid[5]=5 - count = 5 (≥ k), early break

Next: lo=1 hi=9

Target: 5

1

0

lo

2

1

2

2

3

3

3

4

mid/hi

4

5

6

6

6

7

9

8

mid[5]=5 - count = 5 (≥ k)

Next: lo=1 hi=5

Target: 5

1

0

lo

2

1

2

2

mid

3

3

3

4

hi

4

5

6

6

6

7

9

8

mid[3]=3

Next: lo=1 hi=5

Target: 5

1

0

lo

2

1

2

2

mid

3

3

3

4

hi

4

5

6

6

6

7

9

8

mid[3]=3 - count after row 1: 3

Next: lo=1 hi=5

Target: 5

1

0

lo

2

1

2

2

mid

3

3

3

4

hi

4

5

6

6

6

7

9

8

mid[3]=3 - count after row 2: 4

Next: lo=1 hi=5

Target: 5

1

0

lo

2

1

2

2

mid

3

3

3

4

hi

4

5

6

6

6

7

9

8

mid[3]=3 - count = 5 (≥ k)

Next: lo=1 hi=5

Target: 5

1

0

lo

2

1

2

2

mid/hi

3

3

3

4

4

5

6

6

6

7

9

8

mid[3]=3 - count = 5 (≥ k)

Next: lo=1 hi=3

Target: 5

1

0

lo

2

1

mid

2

2

hi

3

3

3

4

4

5

6

6

6

7

9

8

mid[2]=2

Next: lo=1 hi=3

Target: 5

1

0

lo

2

1

mid

2

2

hi

3

3

3

4

4

5

6

6

6

7

9

8

mid[2]=2 - count after row 1: 2

Next: lo=1 hi=3

Target: 5

1

0

lo

2

1

mid

2

2

hi

3

3

3

4

4

5

6

6

6

7

9

8

mid[2]=2 - count after row 2: 3

Next: lo=1 hi=3

Target: 5

1

0

lo

2

1

mid

2

2

hi

3

3

3

4

4

5

6

6

6

7

9

8

mid[2]=2 - count = 3 (< k)

Next: lo=1 hi=3

Target: 5

1

0

2

1

mid

2

2

lo/hi

3

3

3

4

4

5

6

6

6

7

9

8

mid[2]=2 - count = 3 (< k)

Next: lo=3 hi=3

1

0

2

1

2

2

3

3

3

4

4

5

6

6

6

7

9

8

Key Takeaways

✓ Binary search on values, not indices, efficiently finds the kth smallest number in a multiplication table.

This insight is hard to see from code alone because the search is over possible values, not positions.

✓ Counting how many numbers are ≤ mid uses integer division per row, avoiding building the entire table.

This counting method is a clever optimization that reduces complexity drastically.

✓ Early break in counting once count ≥ k saves unnecessary computation and speeds up the algorithm.

The trace shows how early break prevents counting all rows when not needed.

Practice

1. You are given a sorted array and need to find how many times a specific target value appears. Which algorithmic approach guarantees the most efficient solution in terms of time complexity?

easy

A. Binary search to find the left and right boundaries of the target

B. Linear scan through the array counting occurrences

C. Dynamic programming to count occurrences using subproblems

D. Greedy approach selecting elements until target count is found

Solution

1. Step 1: Understand problem constraints

   The array is sorted, so binary search can be used to find boundaries efficiently.

2. Step 2: Identify optimal approach

   Binary search for left and right boundaries finds the first and last occurrence indices in O(log n) time, enabling count calculation by subtraction.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Binary search halves search space each step [OK]

Hint: Sorted array -> binary search boundaries [OK]

Common Mistakes:

• Using linear scan despite sorted array
• Confusing DP with counting occurrences
• Applying greedy which doesn't guarantee correctness

2. Consider the following Python code that finds the smallest divisor for nums = [1, 2, 5, 9] and threshold = 6. What is the value of the variable mid during the first iteration of the while loop inside smallest_divisor?

easy

A. 4

B. 5

C. 3

D. 6

Solution

1. Step 1: Initialize low and high

   low = 1, high = max(nums) = 9

2. Step 2: Calculate mid in first iteration

   mid = (1 + 9) // 2 = 5; integer division yields 5.

3. Step 3: Confirm mid value

   The first mid value is 5, matching 5.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Integer division midpoint between 1 and 9 is 5 -> [OK]

Hint: Mid is integer division of low and high boundaries [OK]

Common Mistakes:

• Off-by-one error in calculating mid
• Confusing mid with low or high values
• Misunderstanding integer division behavior

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

4. Examine the following buggy code snippet for the Split Array Largest Sum problem. Which line contains the subtle bug that can cause incorrect results or infinite loops?

medium

A. Line 7: Missing update of start to end causing infinite loop

B. Line 2: Initialization of count variable

C. Line 5: Using bisect_right to find end index

D. Line 8: Checking if count exceeds m

Solution

1. Step 1: Analyze loop control variables

   The variable start controls the loop progress and must be updated to avoid infinite loops.

2. Step 2: Identify missing update

   Line 7 lacks start = end, so start never advances, causing infinite loop or wrong split counts.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Without updating start, loop never progresses [OK]

Hint: Check loop variables update carefully [OK]

Common Mistakes:

• Forgetting to update loop index after binary search
• Misusing bisect boundaries causing off-by-one errors
• Incorrect initialization of count or start

5. Suppose the problem is modified so that the matrix rows are sorted but columns are not guaranteed to be sorted. Which approach would correctly find the kth smallest element efficiently?

hard

A. Use the min-heap approach merging rows as before, since rows remain sorted.

B. Flatten the matrix and sort it, then return the kth element.

C. Use binary search on the value range with a counting function scanning the entire matrix.

D. Use a min-heap merging columns instead of rows.

Solution

1. Step 1: Analyze matrix properties

   Rows are sorted but columns are not, so min-heap merging rows only partially orders elements.

2. Step 2: Evaluate approaches

   Min-heap merging rows assumes columns sorted for correctness; binary search counting requires sorted rows and columns for efficient counting; flatten and sort works regardless.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Flatten and sort is the fallback when only rows sorted [OK]

Hint: Partial sorting breaks heap and binary search assumptions [OK]

Common Mistakes:

• Assuming min-heap merging rows still works
• Using binary search counting without full sorting
• Ignoring matrix sorting properties