Given three integers n, m, and k. Consider a multiplication table of size n × m (with 1-based indexing), where the value at each cell (i, j) is defined as: mat[i][j] = i × j. That is, the cell at row i and column j contains the product of i and j.
Find the k-th smallest element in this multiplication table.
Examples:
Input: n = 2, m = 3, k = 5
Output: 4
Explanation:
Multiplication Table: [[1, 2, 3],
[2, 4, 6]]
Sorted Elements are [1, 2, 2, 3, 4, 6], then 5th smallest element is 4.Input: n = 3, m = 2, k = 4
Output: 3
Explanation:
Multiplication Table: [[1, 2],
[2, 4],
[3, 6]]
Sorted Elements are [1, 2, 2, 3, 4, 6], then 4th smallest element is 3.
Try it on GfG Practice
Table of Content
[Naive Approach] Checking all Possibilities - O(n × m × log(n × m)) time and O(n × m) space
The approach generates all values in the n × m multiplication table by computing i × j for every cell, stores them in a list, and sorts the list. After sorting, the k-th smallest element is simply the element at index k - 1. This is a brute-force method and works well for small sizes.
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int kthSmallest(int n, int m, int k) {
vector<int> arr;
// try all combinations
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
arr.push_back(i * j);
}
}
// sort the array
sort(arr.begin(), arr.end());
return arr[k - 1];
}
int main() {
int n = 2, m = 3, k = 5;
cout << kthSmallest(n, m, k);
return 0;
}
import java.util.Collections;
class GfG {
public static int kthSmallest(int n, int m, int k) {
ArrayList<Integer> arr = new ArrayList<>();
// try all combinations
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
arr.add(i * j);
}
}
// sort the array
Collections.sort(arr);
return arr.get(k - 1);
}
public static void main(String[] args) {
int n = 2, m = 3, k = 5;
System.out.println(kthSmallest(n, m, k));
}
}
def kthSmallest(n, m, k):
arr = []
# try all combinations
for i in range(1, n + 1):
for j in range(1, m + 1):
arr.append(i * j)
# sort the array
arr.sort()
return arr[k - 1]
if __name__ == "__main__":
n, m, k = 2, 3, 5
print(kthSmallest(n, m, k))
using System;
using System.Collections.Generic;
class GfG {
public static int kthSmallest(int n, int m, int k) {
List<int> arr = new List<int>();
// try all combinations
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
arr.Add(i * j);
}
}
// sort the array
arr.Sort();
return arr[k - 1];
}
public static void Main(string[] args) {
int n = 2, m = 3, k = 5;
Console.WriteLine(kthSmallest(n, m, k));
}
}
function kthSmallest(n, m, k) {
let arr = [];
// try all combinations
for (let i = 1; i <= n; i++) {
for (let j = 1; j <= m; j++) {
arr.push(i * j);
}
}
// sort the array
arr.sort((a, b) => a - b);
return arr[k - 1];
}
// Driver Code
let n = 2, m = 3, k = 5;
console.log(kthSmallest(n, m, k));
Output
4
[Better Approach] Using Max Heap - O(n × m × log(k)) time and O(k) space
The idea is similar to kth Smallest Element using Max Heap. We generate all values of the form (i × j) and maintain a max heap of size k. If the current element is smaller than the largest element in our heap, we replace the largest element with the current one. At the end, the Max Heap root contains kth smallest values.
Step by step implementation:
- Create a max heap data structure to store k smallest elements.
- Iterate through all cells in the n × m table.
- Add elements to the heap until it reaches size k.
- For subsequent elements, if smaller than heap top, replace the largest element.
- Return the top element of the heap which is the kth smallest.
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int kthSmallest(int n, int m, int k) {
priority_queue<int> pq;
// check all combinations
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
// if size of heap is less
// than k.
if (pq.size() < k) {
pq.push(i*j);
}
// else if current value is
// less than heap top.
else if (i*j < pq.top()) {
pq.pop();
pq.push(i*j);
}
}
}
return pq.top();
}
int main() {
int n = 2, m = 3, k = 5;
cout << kthSmallest(n, m, k);
return 0;
}
import java.util.Collections;
import java.util.PriorityQueue;
class GfG {
public static int kthSmallest(int n, int m, int k) {
PriorityQueue<Integer> pq =
new PriorityQueue<>(Collections.reverseOrder());
// check all combinations
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
// if size of heap is less
// than k.
if (pq.size() < k) {
pq.add(i * j);
}
// else if current value is
// less than heap top.
else if (i * j < pq.peek()) {
pq.poll();
pq.add(i * j);
}
}
}
return pq.peek();
}
public static void main(String[] args) {
int n = 2, m = 3, k = 5;
System.out.println(kthSmallest(n, m, k));
}
}
import heapq
def kthSmallest(n, m, k):
pq = []
# check all combinations
for i in range(1, n + 1):
for j in range(1, m + 1):
# if size of heap is less
# than k.
if len(pq) < k:
heapq.heappush(pq, -i * j)
# else if current value is
# less than heap top.
elif i * j < -pq[0]:
heapq.heappop(pq)
heapq.heappush(pq, -i * j)
return -pq[0]
if __name__ == "__main__":
n, m, k = 2, 3, 5
print(kthSmallest(n, m, k))
using System;
using System.Collections.Generic;
class GfG {
public static int kthSmallest(int n, int m, int k) {
// using SortedDictionary as max-heap (reverse sort)
SortedDictionary<int, Queue<int>> maxHeap =
new SortedDictionary<int, Queue<int>>
(Comparer<int>.Create((a, b) => b.CompareTo(a)));
int totalCount = 0;
// check all combinations
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
int val = i * j;
// if size of heap is less than k
if (totalCount < k) {
if (!maxHeap.ContainsKey(val))
maxHeap[val] = new Queue<int>();
maxHeap[val].Enqueue(val);
totalCount++;
}
// else if current value is less than heap top
else {
// get max key
int maxVal = firstKey(maxHeap);
if (val < maxVal) {
maxHeap[maxVal].Dequeue();
if (maxHeap[maxVal].Count == 0)
maxHeap.Remove(maxVal);
if (!maxHeap.ContainsKey(val))
maxHeap[val] = new Queue<int>();
maxHeap[val].Enqueue(val);
}
}
}
}
// return top of max-heap
return firstKey(maxHeap);
}
// helper to get first key of dictionary (max element)
static int firstKey(SortedDictionary<int, Queue<int>> dict){
foreach (var kvp in dict)
return kvp.Key;
return -1;
}
public static void Main(string[] args) {
int n = 2, m = 3, k = 5;
Console.WriteLine(kthSmallest(n, m, k));
}
}
class MaxHeap {
constructor() {
this.heap = [];
}
push(val) {
this.heap.push(val);
this.heap.sort((a, b) => b - a);
}
pop() {
return this.heap.shift();
}
top() {
return this.heap[0];
}
size() {
return this.heap.length;
}
}
function kthSmallest(n, m, k) {
const pq = new MaxHeap();
// check all combinations
for (let i = 1; i <= n; i++) {
for (let j = 1; j <= m; j++) {
// if size of heap is less
// than k.
if (pq.size() < k) {
pq.push(i * j);
}
// else if current value is
// less than heap top.
else if (i * j < pq.top()) {
pq.pop();
pq.push(i * j);
}
}
}
return pq.top();
}
// Driver Code
let n = 2, m = 3, k = 5;
console.log(kthSmallest(n, m, k));
Output
4
[Expected Approach] Using Binary Search - O(n × log (n × m)) time and O(1) space
Instead of generating all n × m elements, we define the search range from 1 to n × m and use binary search to find the value where exactly k elements in the table are smaller than or equal to it. We count smaller values than the current mid value. If the count is more than k, we go the right half, else we go the left half.
How can we count values less than equal to x?
To count values less than or equal to a given number x in the multiplication table, we iterate through each row i from 1 to n and count how many elements in that row are less than or equal to x. For each row i, the elements are i, 2×i, 3×i, ..., m×i, so there are min(x/i, m) such elements in row i.
#include <iostream>
using namespace std;
// function to find the number of
// values less than equal to val.
int count(int val, int n, int m) {
int cnt = 0;
for (int i = 1; i <= n; i++) {
cnt += min(val / i, m);
}
return cnt;
};
int kthSmallest(int n, int m, int k) {
// binary search to find the kth number
int l = 1, h = n * m;
while (l < h) {
int mid = (l + h) / 2;
if (count(mid, n, m) < k) {
l = mid + 1;
} else {
h = mid;
}
}
// return the kth smallest number
return l;
}
int main() {
int n = 2, m = 3, k = 5;
cout << kthSmallest(n, m, k);
return 0;
}
class GfG {
// function to find the number of
// values less than equal to val.
public static int count(int val, int n, int m) {
int cnt = 0;
for (int i = 1; i <= n; i++) {
cnt += Math.min(val / i, m);
}
return cnt;
}
public static int kthSmallest(int n, int m, int k) {
// binary search to find the kth number
int l = 1, h = n * m;
while (l < h) {
int mid = (l + h) / 2;
if (count(mid, n, m) < k) {
l = mid + 1;
} else {
h = mid;
}
}
// return the kth smallest number
return l;
}
public static void main(String[] args) {
int n = 2, m = 3, k = 5;
System.out.println(kthSmallest(n, m, k));
}
}
# function to find the number of
# values less than equal to val.
def count(val, n, m):
cnt = 0
for i in range(1, n + 1):
cnt += min(val // i, m)
return cnt
def kthSmallest(n, m, k):
# binary search to find the kth number
l, h = 1, n * m
while l < h:
mid = (l + h) // 2
if count(mid, n, m) < k:
l = mid + 1
else:
h = mid
# return the kth smallest number
return l
if __name__ == "__main__":
n, m, k = 2, 3, 5
print(kthSmallest(n, m, k))
using System;
class GfG {
// function to find the number of
// values less than equal to val.
public static int count(int val, int n, int m) {
int cnt = 0;
for (int i = 1; i <= n; i++) {
cnt += Math.Min(val / i, m);
}
return cnt;
}
public static int kthSmallest(int n, int m, int k) {
// binary search to find the kth number
int l = 1, h = n * m;
while (l < h) {
int mid = (l + h) / 2;
if (count(mid, n, m) < k) {
l = mid + 1;
} else {
h = mid;
}
}
// return the kth smallest number
return l;
}
public static void Main(string[] args) {
int n = 2, m = 3, k = 5;
Console.WriteLine(kthSmallest(n, m, k));
}
}
// function to find the number of
// values less than equal to val.
function count(val, n, m) {
let cnt = 0;
for (let i = 1; i <= n; i++) {
cnt += Math.min(Math.floor(val / i), m);
}
return cnt;
}
function kthSmallest(n, m, k) {
// binary search to find the kth number
let l = 1, h = n * m;
while (l < h) {
let mid = Math.floor((l + h) / 2);
if (count(mid, n, m) < k) {
l = mid + 1;
} else {
h = mid;
}
}
// return the kth smallest number
return l;
}
// Driver Code
let n = 2, m = 3, k = 5;
console.log(kthSmallest(n, m, k));
Output
4