Kth Smallest Number in Multiplication Table

🎯

Kth Smallest Number in Multiplication Table

hardBINARY_SEARCHGoogleAmazon

Imagine you have a multiplication table of size m x n, and you want to find the kth smallest number in it without generating the entire table. This is like finding a specific product in a huge grid without enumerating all entries.

💡 This problem is a classic example of binary search on the answer space rather than on indices. Beginners often struggle because the table is too large to generate explicitly, so they must think about counting how many numbers are less than or equal to a candidate value efficiently.

📋

Problem Statement

Given integers m, n, and k, find the kth smallest number in the m x n multiplication table where the value at the ith row and jth column is i * j.

1 ≤ m, n ≤ 3 * 10^41 ≤ k ≤ m * n

💡

Example

Input"m = 3, n = 3, k = 5"

Output3

The multiplication table is [[1,2,3],[2,4,6],[3,6,9]]. The sorted elements are [1,2,2,3,3,4,6,6,9]. The 5th smallest is 3.

• m = 1, n = 1, k = 1 → output: 1 (smallest table possible)
• k = 1 → output: 1 (smallest element in any table)
• k = m * n → output: m * n (largest element in the table)
• m and n are large but k is small → output: small number (tests efficiency)

⚠️

Common Mistakes

Trying to generate the entire multiplication table for large inputs

Time limit exceeded or memory overflow

✅ Use binary search on answer space with counting function

Incorrect counting function that does not cap counts by n per row

Overcounts numbers, leading to wrong binary search decisions

✅ Use min(n, x // i) to count numbers ≤ x in each row

Not handling integer division carefully in counting or mid calculation

Wrong counts or infinite loops in binary search

✅ Use floor division and safe mid calculation (low + (high - low) // 2)

Not breaking early in counting when count ≥ k

Slower runtime, possibly timing out on large inputs

✅ Add early break in counting function once count reaches or exceeds k

🧠

Brute Force (Generate and Sort Entire Table)

💡 This approach exists to build intuition by directly simulating the problem. It is straightforward but inefficient, helping beginners understand the problem structure before optimizing.

Intuition

Generate all elements of the multiplication table, store them in a list, sort the list, and return the kth smallest element.

Algorithm

1. Initialize an empty list to hold all multiplication table values.
2. Use two nested loops to generate all values i*j for i in [1..m], j in [1..n].
3. Sort the list of all values.
4. Return the element at index k-1.

💡 The nested loops and sorting are easy to understand but lead to inefficiency because the table size can be huge.

</>

Code

def findKthNumber(m, n, k):
    vals = []
    for i in range(1, m+1):
        for j in range(1, n+1):
            vals.append(i*j)
    vals.sort()
    return vals[k-1]

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

Line Notes

vals = []Initialize list to store all multiplication values

for i in range(1, m+1)Outer loop over rows of the table

for j in range(1, n+1)Inner loop over columns of the table

vals.append(i*j)Calculate and store each multiplication value

vals.sort()Sort all values to find kth smallest easily

return vals[k-1]Return kth smallest element (0-based indexing)

import java.util.*;
public class Solution {
    public static int findKthNumber(int m, int n, int k) {
        List<Integer> vals = new ArrayList<>();
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                vals.add(i * j);
            }
        }
        Collections.sort(vals);
        return vals.get(k - 1);
    }

    public static void main(String[] args) {
        System.out.println(findKthNumber(3, 3, 5)); // Output: 3
    }
}

Line Notes

List<Integer> vals = new ArrayList<>()Create list to hold multiplication values

for (int i = 1; i <= m; i++)Outer loop over rows

for (int j = 1; j <= n; j++)Inner loop over columns

vals.add(i * j)Add product to list

Collections.sort(vals)Sort list to find kth smallest

return vals.get(k - 1)Return kth smallest element

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

int findKthNumber(int m, int n, int k) {
    vector<int> vals;
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            vals.push_back(i * j);
        }
    }
    sort(vals.begin(), vals.end());
    return vals[k - 1];
}

int main() {
    cout << findKthNumber(3, 3, 5) << endl; // Output: 3
    return 0;
}

Line Notes

vector<int> vals;Vector to store all multiplication values

for (int i = 1; i <= m; i++)Outer loop over rows

for (int j = 1; j <= n; j++)Inner loop over columns

vals.push_back(i * j);Add product to vector

sort(vals.begin(), vals.end());Sort vector to find kth smallest

return vals[k - 1];Return kth smallest element

function findKthNumber(m, n, k) {
    const vals = [];
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            vals.push(i * j);
        }
    }
    vals.sort((a, b) => a - b);
    return vals[k - 1];
}

// Test
console.log(findKthNumber(3, 3, 5)); // Output: 3

Line Notes

const vals = []Initialize array to hold multiplication values

for (let i = 1; i <= m; i++)Outer loop over rows

for (let j = 1; j <= n; j++)Inner loop over columns

vals.push(i * j)Add product to array

vals.sort((a, b) => a - b)Sort array numerically to find kth smallest

return vals[k - 1]Return kth smallest element

⏱

Complexity

TimeO(m * n log(m * n))

SpaceO(m * n)

We generate all m*n elements and sort them, sorting dominates with O(m*n log(m*n)) time. Space is O(m*n) for storing all elements.

💡 For m=n=1000, this means 1,000,000 elements and sorting them, which is about 20 million operations - too slow for large inputs.

Interview Verdict: TLE

This approach times out on large inputs because it tries to generate and sort the entire table, which is too big.

🧠

Binary Search on Answer Space with Counting Function

💡 This approach introduces the key insight: instead of enumerating all values, we binary search the value range and count how many numbers are ≤ mid. This is a classic technique for problems where direct enumeration is impossible.

Intuition

The smallest number is 1 and the largest is m*n. We binary search this range. For each mid, count how many numbers in the table are ≤ mid. If count < k, move low up; else move high down.

Algorithm

1. Set low = 1 and high = m * n (max possible value).
2. While low < high:
3. Compute mid = (low + high) // 2.
4. Count how many numbers in the table are ≤ mid using countLessEqual(mid).
5. If count < k, set low = mid + 1; else set high = mid.
6. Return low as the kth smallest number.

💡 The counting function is the core optimization, replacing enumeration with O(m) counting per guess.

</>

Code

def findKthNumber(m, n, k):
    def countLessEqual(x):
        count = 0
        for i in range(1, m+1):
            count += min(n, x // i)
        return count

    low, high = 1, m * n
    while low < high:
        mid = (low + high) // 2
        if countLessEqual(mid) < k:
            low = mid + 1
        else:
            high = mid
    return low

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

Line Notes

def countLessEqual(x):Helper to count numbers ≤ x in table

for i in range(1, m+1):Iterate over rows to count per row

count += min(n, x // i)Count how many in row i are ≤ x (bounded by n)

low, high = 1, m * nInitialize binary search range

while low < high:Binary search loop to narrow answer

mid = (low + high) // 2Midpoint guess in answer space

if countLessEqual(mid) < k:If fewer than k numbers ≤ mid, increase low

else: high = midOtherwise, decrease high to mid

public class Solution {
    public static int findKthNumber(int m, int n, int k) {
        int low = 1, high = m * n;
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (countLessEqual(m, n, mid) < k) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return low;
    }

    private static int countLessEqual(int m, int n, int x) {
        int count = 0;
        for (int i = 1; i <= m; i++) {
            count += Math.min(n, x / i);
        }
        return count;
    }

    public static void main(String[] args) {
        System.out.println(findKthNumber(3, 3, 5)); // Output: 3
    }
}

Line Notes

int low = 1, high = m * n;Initialize binary search range

while (low < high)Loop to narrow down answer

int mid = low + (high - low) / 2;Calculate mid to avoid overflow

if (countLessEqual(m, n, mid) < k)Check if mid is too small

low = mid + 1;Increase low if count less than k

else { high = mid; }Decrease high otherwise

for (int i = 1; i <= m; i++)Count numbers ≤ x row-wise

count += Math.min(n, x / i);Add count for row i bounded by n

#include <iostream>
#include <algorithm>
using namespace std;

int countLessEqual(int m, int n, int x) {
    int count = 0;
    for (int i = 1; i <= m; i++) {
        count += min(n, x / i);
    }
    return count;
}

int findKthNumber(int m, int n, int k) {
    int low = 1, high = m * n;
    while (low < high) {
        int mid = low + (high - low) / 2;
        if (countLessEqual(m, n, mid) < k) {
            low = mid + 1;
        } else {
            high = mid;
        }
    }
    return low;
}

int main() {
    cout << findKthNumber(3, 3, 5) << endl; // Output: 3
    return 0;
}

Line Notes

int countLessEqual(int m, int n, int x)Function to count numbers ≤ x

for (int i = 1; i <= m; i++)Iterate rows to count per row

count += min(n, x / i);Count elements ≤ x in row i

int low = 1, high = m * n;Initialize binary search range

while (low < high)Binary search loop

int mid = low + (high - low) / 2;Calculate mid safely

if (countLessEqual(m, n, mid) < k)Check if mid too small

low = mid + 1;Increase low if count less than k

else { high = mid; }Decrease high otherwise

function findKthNumber(m, n, k) {
    function countLessEqual(x) {
        let count = 0;
        for (let i = 1; i <= m; i++) {
            count += Math.min(n, Math.floor(x / i));
        }
        return count;
    }

    let low = 1, high = m * n;
    while (low < high) {
        let mid = Math.floor((low + high) / 2);
        if (countLessEqual(mid) < k) {
            low = mid + 1;
        } else {
            high = mid;
        }
    }
    return low;
}

// Test
console.log(findKthNumber(3, 3, 5)); // Output: 3

Line Notes

function countLessEqual(x)Helper to count numbers ≤ x

for (let i = 1; i <= m; i++)Iterate rows to count per row

count += Math.min(n, Math.floor(x / i));Count elements ≤ x in row i

let low = 1, high = m * n;Initialize binary search range

while (low < high)Binary search loop

let mid = Math.floor((low + high) / 2);Calculate mid value

if (countLessEqual(mid) < k)Check if mid too small

low = mid + 1;Increase low if count less than k

else { high = mid; }Decrease high otherwise

⏱

Complexity

TimeO(m * log(m * n))

SpaceO(1)

Each binary search iteration takes O(m) to count, and binary search runs in O(log(m*n)) steps.

💡 For m=30000 and n=30000, this is about 30,000 * 30 ≈ 900,000 operations, which is efficient enough.

Interview Verdict: Accepted

This approach is efficient and passes all tests by cleverly searching the answer space and counting without enumerating all values.

🧠

Optimized Binary Search with Early Break in Counting

💡 This approach improves the counting function by breaking early when counts exceed k, saving time in practice. It is a practical optimization of approach 2.

Intuition

While counting how many numbers are ≤ mid, stop counting once count exceeds k since we only need to know if count < k or not.

Algorithm

1. Set low = 1 and high = m * n.
2. While low < high:
3. Compute mid = (low + high) // 2.
4. Count numbers ≤ mid with early break if count > k.
5. If count < k, set low = mid + 1; else set high = mid.
6. Return low.

💡 Early break avoids unnecessary counting once we know mid is too small.

</>

Code

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

    low, high = 1, m * n
    while low < high:
        mid = (low + high) // 2
        if countLessEqual(mid) < k:
            low = mid + 1
        else:
            high = mid
    return low

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

Line Notes

def countLessEqual(x):Counting function with early break

for i in range(1, m+1):Iterate rows

count += min(n, x // i)Add count for row i

if count >= k:Stop early if count already enough

breakBreak loop to save time

low, high = 1, m * nInitialize binary search range

while low < high:Binary search loop

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

if countLessEqual(mid) < k:Check if mid too small

low = mid + 1Increase low if needed

else: high = midDecrease high otherwise

public class Solution {
    public static int findKthNumber(int m, int n, int k) {
        int low = 1, high = m * n;
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (countLessEqual(m, n, mid, k) < k) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return low;
    }

    private static int countLessEqual(int m, int n, int x, int k) {
        int count = 0;
        for (int i = 1; i <= m; i++) {
            count += Math.min(n, x / i);
            if (count >= k) {
                break;
            }
        }
        return count;
    }

    public static void main(String[] args) {
        System.out.println(findKthNumber(3, 3, 5)); // Output: 3
    }
}

Line Notes

int low = 1, high = m * n;Initialize binary search range

while (low < high)Binary search loop

int mid = low + (high - low) / 2;Calculate mid safely

if (countLessEqual(m, n, mid, k) < k)Check if mid too small

low = mid + 1;Increase low if count less than k

else { high = mid; }Decrease high otherwise

for (int i = 1; i <= m; i++)Count numbers row-wise

count += Math.min(n, x / i);Add count for row i

if (count >= k) { break; }Early break to save time

#include <iostream>
#include <algorithm>
using namespace std;

int countLessEqual(int m, int n, int x, int k) {
    int count = 0;
    for (int i = 1; i <= m; i++) {
        count += min(n, x / i);
        if (count >= k) break;
    }
    return count;
}

int findKthNumber(int m, int n, int k) {
    int low = 1, high = m * n;
    while (low < high) {
        int mid = low + (high - low) / 2;
        if (countLessEqual(m, n, mid, k) < k) {
            low = mid + 1;
        } else {
            high = mid;
        }
    }
    return low;
}

int main() {
    cout << findKthNumber(3, 3, 5) << endl; // Output: 3
    return 0;
}

Line Notes

int countLessEqual(int m, int n, int x, int k)Counting with early break

for (int i = 1; i <= m; i++)Iterate rows

count += min(n, x / i);Add count for row i

if (count >= k) break;Stop counting early if enough

int low = 1, high = m * n;Initialize binary search range

while (low < high)Binary search loop

int mid = low + (high - low) / 2;Calculate mid

if (countLessEqual(m, n, mid, k) < k)Check if mid too small

low = mid + 1;Increase low if needed

else { high = mid; }Decrease high otherwise

function findKthNumber(m, n, k) {
    function countLessEqual(x) {
        let count = 0;
        for (let i = 1; i <= m; i++) {
            count += Math.min(n, Math.floor(x / i));
            if (count >= k) break;
        }
        return count;
    }

    let low = 1, high = m * n;
    while (low < high) {
        let mid = Math.floor((low + high) / 2);
        if (countLessEqual(mid) < k) {
            low = mid + 1;
        } else {
            high = mid;
        }
    }
    return low;
}

// Test
console.log(findKthNumber(3, 3, 5)); // Output: 3

Line Notes

function countLessEqual(x)Counting function with early break

for (let i = 1; i <= m; i++)Iterate rows

count += Math.min(n, Math.floor(x / i));Add count for row i

if (count >= k) break;Stop counting early if enough

let low = 1, high = m * n;Initialize binary search range

while (low < high)Binary search loop

let mid = Math.floor((low + high) / 2);Calculate mid

if (countLessEqual(mid) < k)Check if mid too small

low = mid + 1;Increase low if needed

else { high = mid; }Decrease high otherwise

⏱

Complexity

TimeO(m * log(m * n)) with early break optimization

SpaceO(1)

Early break reduces average counting time, improving practical runtime though worst-case remains same.

💡 This optimization helps especially when k is small, avoiding full row scans.

Interview Verdict: Accepted

This is a practical improvement over approach 2, often used in interviews to show attention to efficiency.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, always code the binary search on answer space with counting (Approach 2 or 3). Brute force is only for explanation.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(m * n log(m * n))	O(m * n)	No	N/A	Mention only - never code due to inefficiency
2. Binary Search on Answer Space	O(m * log(m * n))	O(1)	No	N/A	Code this as optimal solution
3. Optimized Binary Search with Early Break	O(m * log(m * n)) (faster in practice)	O(1)	No	N/A	Mention as optimization if time permits

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before your interview. Start by clarifying the problem, then explain the brute force approach to show understanding. Next, present the binary search on answer space with counting, and finally mention optimizations. Practice coding and testing thoroughly.

How to Present

Step 1: Clarify the problem and constraints.Step 2: Describe the brute force approach to demonstrate understanding.Step 3: Introduce binary search on the answer space and explain the counting function.Step 4: Discuss optimizations like early break in counting.Step 5: Code the optimal solution and test with examples.

Time Allocation

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

What the Interviewer Tests

The interviewer tests your ability to recognize binary search on answer space, implement an efficient counting function, and optimize for large inputs. They also check your problem-solving clarity and coding correctness.

Common Follow-ups

• What if m and n are very large but k is small? → Early break optimization helps.
• Can you find the kth largest instead? → Adjust binary search accordingly.

💡 These follow-ups test your understanding of the binary search approach and your ability to adapt it to variations.

🔍

Pattern Recognition

When to Use

1) Problem asks for kth smallest/largest in a virtual sorted structure. 2) Direct enumeration is too large. 3) You can count how many elements ≤ x efficiently. 4) The answer lies in a numeric range.

Signature Phrases

'kth smallest number in multiplication table''count how many numbers are less than or equal to mid'

NOT This Pattern When

Problems that require sorting or heap-based selection without counting or binary searching the answer space.

Similar Problems

Find Kth Smallest Pair Distance - binary search on answer space with counting pairsMedian of Two Sorted Arrays - binary search on partition indicesKth Smallest Element in a Sorted Matrix - binary search on value range with counting

Practice

1. You are given a 2D matrix where each row is sorted in ascending order from left to right, and each column is sorted in ascending order from top to bottom. You need to determine if a target value exists in the matrix. Which approach guarantees the most efficient search in this scenario?

easy

A. Perform a binary search on each row individually to find the target.

B. Use a brute force nested loop to check every element until the target is found.

C. Start from the bottom-left corner and move only upwards or rightwards to find the target.

D. Use dynamic programming to build a table of reachable values and check for the target.

Solution

1. Step 1: Understand matrix properties

   Each row and column is sorted ascending, allowing binary search on rows.

2. Step 2: Evaluate approaches

   Brute force is O(m*n), bottom-left approach is staircase search but not binary search, DP is unrelated here. Binary search on each row yields O(m*log n) time.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Binary search on rows exploits sorted rows efficiently [OK]

Hint: Sorted rows allow binary search per row [OK]

Common Mistakes:

• Confusing staircase search with binary search on rows
• Assuming DP applies here
• Thinking brute force is optimal

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. What is the time complexity of the optimal solution using binary search on the answer space combined with the feasibility check for the Koko Eating Bananas problem, where n is the number of piles and m is the maximum pile size?

medium

A. O(n * m) -- linear search over speeds times piles

B. O(n + log m) -- linear pass plus binary search overhead

C. O(log n * m) -- binary search over piles with linear speed check

D. O(n * log m) -- binary search over speeds with linear feasibility check

Solution

1. Step 1: Identify outer and inner loops

   The binary search runs over the speed range [1..m], which takes O(log m) iterations.

2. Step 2: Analyze feasibility check cost

   Each feasibility check iterates over all n piles, costing O(n) time.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Binary search log m times feasibility O(n) -> O(n log m) [OK]

Hint: Binary search log m times linear feasibility check [OK]

Common Mistakes:

• Confusing n and m in complexity
• Assuming binary search on piles array

4. Consider the following buggy code for the Koko Eating Bananas problem. Which line contains the subtle bug that can cause incorrect results on some inputs?

from math import ceil

def can_finish(piles, speed, h):
    hours = 0
    for pile in piles:
        hours += pile // speed  # Line 6
        if hours > h:
            return false
    return true

def minEatingSpeed(piles, h):
    low, high = 1, max(piles)
    while low < high:
        mid = (low + high) // 2
        if can_finish(piles, mid, h):
            high = mid
        else:
            low = mid + 1
    return low

medium

A. Line 9: Returning true when hours <= h

B. Line 3: import statement

C. Line 6: Using floor division instead of ceiling division

D. Line 14: Updating low to mid + 1

Solution

1. Step 1: Identify how hours are calculated

   Line 6 uses floor division (pile // speed), which underestimates hours needed because partial piles still require a full hour.

2. Step 2: Understand impact on feasibility

   Underestimating hours causes can_finish to return true incorrectly, leading to wrong minimum speed.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Replacing floor division with ceiling fixes the bug [OK]

Hint: Hours must be ceil(pile / speed), not floor division [OK]

Common Mistakes:

• Using floor division instead of ceiling
• Misinterpreting feasibility condition

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