C++ Coding Test Course, Finding the Kth Number in an Array

Today, we will learn about one of the frequently asked problems in C++ coding tests, “Finding the Kth Smallest Number in an Array.” The goal of this problem is to find the Kth smallest number in a sorted array. We will analyze how to solve this problem step by step through an example.

Problem Description

Write a program to find the Kth smallest number in the given array. Assume that the elements of the array are distinct integers ranging from 1 to N.

Input

  • The first line contains the size of the array N and K. (1 ≤ N ≤ 100,000, 1 ≤ K ≤ N)
  • The second line contains N integers.

Output

Output the Kth smallest number.

Example

Input Example:

5 2
9 3 1 5 2

Output Example:

2

Problem Solving Strategy

The necessary steps to solve this problem are as follows:

  1. Sort the given array.
  2. Find the K-1 (indexing from 0) element.
  3. Print that value.

C++ Code Implementation

Now, let’s implement the C++ code to solve the given problem. To sort an array in C++, we can use the std::sort function. Below is the code applying that algorithm:

#include 
#include 
#include 

int main() {
    int N, K;
    std::cin >> N >> K; // Input N and K
    std::vector arr(N); // Create an array of size N

    for (int i = 0; i < N; ++i) {
        std::cin >> arr[i]; // Input array elements
    }

    std::sort(arr.begin(), arr.end()); // Sort the array

    std::cout << arr[K - 1] << std::endl; // Output the Kth number (0-indexed)
    return 0;
}

Code Explanation

The above code operates in the following manner:

  1. First, include the iostream, vector, and algorithm libraries. The former is needed for input and output, while the latter is needed for sorting the array.
  2. Declare variables N and K and receive input from the user.
  3. Create an integer vector arr of size N and input the array elements from the user.
  4. Sort the vector using the std::sort function.
  5. Output the Kth smallest number. Since array indexing starts from 0, K - 1 is used.

Complexity Analysis

The time complexity of this algorithm mainly arises from the sorting process. C++’s std::sort has an average time complexity of O(N log N), so the overall time complexity of the algorithm is O(N log N). The space complexity requires O(N) to store the input array.

Additional Problems

You can modify such problems to solve various difficulties. For example:

  • When duplicate elements are present
  • Finding the Kth largest number
  • Finding the Kth number in a subarray

Remember that by slightly modifying the logic for each case, you can easily adapt to them.

Conclusion

In this post, we learned how to find the Kth number in an array. Through the problem-solving process and C++ implementation, we could learn about basic sorting algorithms and how to handle arrays. I encourage you to practice various variant problems. I hope this helps you prepare for your coding tests!