C Programming: K^th smallest number in a multiplication table

Last update on March 20 2025 12:35:27 (UTC/GMT +8 hours)

34. kth Smallest in Multiplication Table Variants

Write a C program that creates a multiplication table of size m x n using integers where 1 <= k <= m * n. Return the k^th smallest element in the said multiplication table.

In mathematics, a multiplication table is a mathematical table used to define a multiplication operation for an algebraic system. The decimal multiplication table was traditionally taught as an essential part of elementary arithmetic around the world, as it lays the foundation for arithmetic operations with base-ten numbers.

Test Data:
(3,3,8) -> 6
(2,3,4) -> 3

Sample Solution:

C Code:

#include <stdio.h> // Include standard input-output library
#include <math.h> // Include math library

// Function to find the minimum of two numbers
int min(int a, int b)
{
    return (a > b) ? b : a; // Return the smaller of the two numbers
}

// Function to find the kth smallest element in m x n multiplication table
int test(int m, int n, int k) {
    if ((k < 1) || (k > m * n)) // Check if k is out of range
        return 0; // Return 0 if k is out of range (false)
        
    int s, p, mid, t; // Declare variables for binary search
    s = 1, p = n * m; // Initialize start and end points for binary search
    
    // Binary search to find the kth smallest element
    while (s <= p) {
        mid = s + floor((p - s) / 2); // Calculate the middle element
        t = 0; // Initialize t to 0
        
        // Loop through each row of the multiplication table
        for (int i = 1; i <= m; i++) {
            t += min(floor(mid / i), n); // Calculate the number of elements less than or equal to mid in the current row
        }
                
        if (t >= k) {
            p = mid - 1; // Update end point if the count is greater than or equal to k
        } else {
            s = mid + 1; // Update start point if the count is less than k
        }
    }
    return s; // Return the kth smallest element
}

int main(void) {
    int m = 3; // Initialize m
    int n = 3; // Initialize n
    int k = 8; // Initialize k
    printf("m = %d, n = %d  k = %d", m, n, k); // Print the values of m, n, and k
    printf("\nkth smallest element in m x n multiplication table = %d", test(m, n, k)); // Print the result of test function
    
    // Test case 2
    m = 2; // Update m
    n = 3; // Update n
    k = 4; // Update k
    printf("\n\nm = %d, n = %d  k = %d", m, n, k); // Print the updated values of m, n, and k
    printf("\nkth smallest element in m x n multiplication table = %d", test(m, n, k)); // Print the result of test function
    
    return 0; // Return 0 to indicate successful execution
}

Sample Output:

m = 3, n = 3  k = 8
kth smallest element in m x n multiplication table = 6
m = 2, n = 3  k = 4
kth smallest element in m x n multiplication table = 3

Flowchart:

For more Practice: Solve these Related Problems:

• Write a C program to generate an m x n multiplication table and find the kth smallest element using binary search.
• Write a C program to simulate the multiplication table and then efficiently extract the kth smallest number.
• Write a C program to calculate the kth smallest element in a multiplication table by counting elements less than a target value.
• Write a C program to optimize the kth smallest search in a multiplication table using a min-heap approach.

C Programming Code Editor:

Click to Open Editor

Improve this sample solution and post your code through Disqus.

Previous: Count the digits in a number that divide it.
Next: Find all prime factors of a given integer.