C++ Coding Test Course, Finding the K-th Number

Hello! In this post, we will discuss one of the coding test problems using C++, titled “Finding the Kth Smallest Number.” The problem of finding the Kth smallest number is something that one might ponder in real life, such as when picking up coupons, and it is frequently encountered in algorithm problem-solving. In this post, I will explain in detail from the problem definition to the solution process and the C++ code implementation.

Problem Definition

Given an array of integers, the problem is to find the Kth smallest number in this array. Here, K is an integer starting from 1, representing the first smallest number, the second smallest number, and so on.

For example, let’s consider the following input:

Array: [3, 1, 2, 4, 5]
K: 3

The 3rd smallest number in the given array is 3. Therefore, the answer in this case is 3.

Input Format

  • First line: Length of the array N (1 <= N <= 100,000)
  • Second line: Integer array A (1 <= A[i] <= 10^9)
  • Third line: Integer K (1 <= K <= N)

Output Format

Print the Kth smallest number.

Problem Solving Plan

We can think of several algorithms that could be used to solve this problem.

  • Sorting: Sort the array and return the Kth index.
  • Using a Min-Heap: A heap can be used to find the Kth smallest number.
  • Quick Select Algorithm: An algorithm that can find the Kth number with an average time complexity of O(N).

Here, we will implement the solution using the most intuitive and easy-to-understand method of sorting the array.

Implementation

First, we will receive the array input using C++’s vector, and sort it using the sort() function. After that, we will structure the program to print the Kth number.

Code Implementation

#include 
#include 
#include  // include for sort()
using namespace std;

int main() {
    int N, K;
    
    // Input the size of the array N
    cout << "Please enter the length of the array N: ";
    cin >> N;

    vector A(N);
    
    // Input for array A
    cout << "Please enter the integer array A (separated by spaces): ";
    for(int i = 0; i < N; i++) {
        cin >> A[i];
    }
    
    // Input K value
    cout << "Please enter the K value: ";
    cin >> K;

    // Sort the array
    sort(A.begin(), A.end());

    // Print the Kth number (index K-1)
    cout << K << "th number is: " << A[K - 1] << endl;

    return 0;
}

Code Explanation

The code operates in the following flow:

  1. It prompts the user to input the length of the array N.
  2. A vector A of integer type with length N is created.
  3. The elements of array A are input by the user.
  4. The K value is input.
  5. Array A is sorted in ascending order.
  6. The Kth number is printed. In C++, since indexing starts from 0, K-1 must be used.

Code Analysis

The input for the problem can go up to 100,000 elements, and in the worst case, a sorting operation with a time complexity of O(N log N) will be performed. After sorting, the Kth number can be found in O(1) time, so the overall time complexity is O(N log N). This complexity is sufficient to be solved within the given time limits.

Test Cases

Let’s consider some test cases to verify the above code:

Test Case 1

Input:
5
3 1 2 4 5
3
Output:
The 3rd number is: 3

Test Case 2

Input:
10
10 9 8 7 6 5 4 3 2 1
5
Output:
The 5th number is: 5

Test Case 3

Input:
5
1 10000 500 999 1000
2
Output:
The 2nd number is: 500

Results and Optimization

We have implemented a basic solution. The method using sorting is intuitive and easy to implement; however, other methods may be required if the size of the array is very large. For example, we could use the Quick Select algorithm. The Quick Select algorithm has an average performance of O(N) and can be useful when memory is constrained.

Overview of Quick Select Algorithm

The Quick Select algorithm is a type of divide-and-conquer algorithm that selects a random pivot to divide the array into two parts, determining which part contains the Kth number and continues searching only in that part. It can quickly find the Kth number even in very large arrays.

Example of Quick Select Implementation

#include <iostream>
#include <vector>
#include <cstdlib> // for rand() function
using namespace std;

// Quick Select algorithm that finds the Kth number in the array
int quickSelect(vector& A, int left, int right, int K) {
    if (left == right) return A[left];

    int pivotIndex = left + rand() % (right - left);
    int pivotValue = A[pivotIndex];

    // Move pivot to the end of the array
    swap(A[pivotIndex], A[right]);
    int storeIndex = left;

    for (int i = left; i < right; i++) {
        if (A[i] < pivotValue) {
            swap(A[storeIndex], A[i]);
            storeIndex++;
        }
    }

    // Move pivot to its final place
    swap(A[storeIndex], A[right]);

    if (K == storeIndex) return A[K];
    else if (K < storeIndex) return quickSelect(A, left, storeIndex - 1, K);
    else return quickSelect(A, storeIndex + 1, right, K);
}

int main() {
    int N, K;

    cout << "Please enter the length of the array N: ";
    cin >> N;

    vector A(N);
    
    cout << "Please enter the integer array A (separated by spaces): ";
    for(int i = 0; i < N; i++) {
        cin >> A[i];
    }

    cout << "Please enter the K value: ";
    cin >> K;

    int result = quickSelect(A, 0, N - 1, K - 1);
    cout << K << "th number is: " << result << endl;

    return 0;
}

Conclusion

Today, we explored how to solve the problem of finding the Kth number using C++. We implemented a basic method of sorting the array to find the Kth number, and briefly discussed the more efficient Quick Select algorithm. Problems like these often appear in coding tests, so it is beneficial to learn them repeatedly. I hope this helps you to develop a basic understanding of algorithms and improve your C++ programming skills.

Thank you for reading! If you have any additional questions, please leave a comment.