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

Hello, everyone preparing for coding tests! Today, we will discuss a problem where we need to find the K-th largest number in an array. This problem is one of the common types that frequently appears in coding tests and is very helpful in understanding the concepts of arrays and sorting. In this article, we will explain the problem in detail and step by step, we will explore how to solve it using C#.

Problem Description

We have a problem of finding the K-th largest number in a given array. The array consists of integers, and K is an index starting from 1. It is assumed that the objects are sorted in size order. For example, if the array is [3, 1, 2, 4, 5] and K is 2, then the 2nd largest number is 4.

Input

  • The first line contains the size of the array N (1 ≤ N ≤ 1000).
  • The second line contains N integers. (Each integer is -10000 ≤ x ≤ 10000)
  • The third line contains the integer K. (1 ≤ K ≤ N)

Output

Print the K-th largest number.

Example Input

5
3 1 2 4 5
2

Example Output

4

Approach to the Problem

To solve this problem, we can follow these steps:

  1. Sort the given array.
  2. Find the K-th largest number in the sorted array.

Step 1: Sort the Array

There are several ways to sort an array, but we can use the Array.Sort() method provided by C#. This method sorts the array in ascending order by default.

Step 2: Find the K-th Number

Finding the K-th number in the sorted array is quite simple. If K is 2, the K-th number will be the one located at the index K – 1 in the sorted array.

C# Code Implementation

Now let’s implement the C# code based on the above methods:


using System;

class KthLargestNumber
{
    static void Main()
    {
        // Get input
        int N = int.Parse(Console.ReadLine());
        int[] arr = new int[N];

        string[] input = Console.ReadLine().Split();
        for (int i = 0; i < N; i++)
        {
            arr[i] = int.Parse(input[i]);
        }

        int K = int.Parse(Console.ReadLine());

        // Sort the array
        Array.Sort(arr);

        // Find the K-th number
        Console.WriteLine(arr[N - K]);
    }
}

Code Explanation

1. The using System; statement allows us to use various classes from the System namespace.

2. int N = int.Parse(Console.ReadLine()); reads the input from the first line and stores the size of the array N.

3. int[] arr = new int[N]; declares an integer array of length N.

4. Console.ReadLine().Split(); method receives the input from the second line and stores the space-separated strings in an array.

5. Array.Sort(arr); sorts the array in ascending order.

6. Console.WriteLine(arr[N - K]); prints the K-th largest number. Here, the number at the index N – K corresponds to the K-th largest number.

Time Complexity Analysis

The time complexity of this problem is determined by the process of sorting the array. The time complexity of the sorting algorithm is O(N log N) in the worst case. The process of finding the K-th number takes O(1), so the overall time complexity is O(N log N).

Conclusion

In this tutorial, we learned how to find the K-th number in an array. We learned to use array sorting and indexing to solve the problem. This problem frequently appears in coding tests, so I encourage you to solve various variations to improve your skills. I will return with more informative topics in the next tutorial. Thank you!

References