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

Problem Description

Given an array arr and an integer K, the task is to find and return the K-th smallest number. The array uses zero-based indexing, and if there are multiple instances of the same number, any one of the K-th smallest numbers may be returned.

For example, if the array is [7, 10, 4, 3, 20, 15] and K=3, the 3rd smallest number is 7.

Input Format

The input is given in the following format:

• First line: Size of the array N (1 <= N <= 10^6)
• Second line: N integers (elements of the array range from -10^9 to 10^9)
• Third line: An integer K (1 <= K <= N)

Input Example

6
7 10 4 3 20 15
3
        

Output Format

The output should be the K-th smallest number in the array.

Output Example

7
        

Solution Process

Step 1: Understanding the Problem

We need to find the K-th smallest number in the given array. Since the array is not sorted, we need to find the value of the K-th element in a sorted state.

Step 2: Choosing the Algorithm

The most intuitive method is to sort the array and then return the K-th element. However, this method has a time complexity of O(N log N). There are various methods to optimize this:

• Quickselect algorithm (average O(N) time complexity)
• Using a heap data structure

In this tutorial, we will be using the Quickselect method.

Step 3: Quickselect Explanation

Quickselect is similar to the Quick Sort algorithm, which selects a pivot to divide the array into left and right parts. The result is derived based on the position of K.

Process of Quickselect

1. Select a pivot value.
2. Move values less than or equal to the pivot to the left and those greater to the right.
3. If K is equal to the pivot index, return the pivot.
4. If K is less than the pivot, recursively call Quickselect on the left part.
5. If K is greater than the pivot, recursively call Quickselect on the right part.

C# Code Implementation

using System;
using System.Linq;

class KthSmallest
{
    public static int QuickSelect(int[] arr, int left, int right, int k)
    {
        if (left == right) // If the array has only one element
            return arr[left];

        Random random = new Random();
        int pivotIndex = left + random.Next(right - left);
        int pivot = arr[pivotIndex];

        // Move pivot to the far right
        Swap(arr, pivotIndex, right);
        int storeIndex = left;

        for (int i = left; i < right; i++)
        {
            if (arr[i] < pivot)
            {
                Swap(arr, storeIndex, i);
                storeIndex++;
            }
        }

        Swap(arr, storeIndex, right); // Place pivot in its correct position

        if (k == storeIndex) return arr[k];
        else if (k < storeIndex) return QuickSelect(arr, left, storeIndex - 1, k);
        else return QuickSelect(arr, storeIndex + 1, right, k);
    }

    private static void Swap(int[] arr, int i, int j)
    {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    static void Main()
    {
        int N = int.Parse(Console.ReadLine());
        int[] arr = Console.ReadLine().Split().Select(int.Parse).ToArray();
        int K = int.Parse(Console.ReadLine()) - 1; // Convert K to a 0-based index

        int result = QuickSelect(arr, 0, N - 1, K);
        Console.WriteLine(result);
    }
}
        

Code Explanation

The above C# code uses the Quickselect algorithm to find the K-th number:

• QuickSelect method: Finds and returns the K-th smallest number in the array.
• Swap method: Swaps the positions of two elements.
• Main: Receives input and executes the program.

This algorithm has an average time complexity of O(N), which is very efficient.

Conclusion

In this tutorial, we learned how to solve the ‘Finding the K-th number’ problem using C#. By practicing the Quickselect algorithm, we have acquired a useful technique for coding interviews. Additionally, I encourage you to experience various algorithms and problems to further enhance your skills.