C Programming: Kth 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 kth 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.
What is the difficulty level of this exercise?
Test your Programming skills with w3resource's quiz.
It will be nice if you may share this link in any developer community or anywhere else, from where other developers may find this content. Thanks.
https://www.w3resource.com/c-programming-exercises/math/c-math-exercise-34.php
- Weekly Trends and Language Statistics
- Weekly Trends and Language Statistics