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

C Programming Mathematics: Exercise-34 with Solution

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:

C Programming Code 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.