python coding test course, finding the Kth number in an array

In this course, we will discuss how to solve the problem of finding the Kth number in an array. This problem is frequently addressed in coding tests and presents a good opportunity to develop skills in efficient algorithm design and implementation.

Problem Description

Given an integer array and an integer K, the task is to sort the array in ascending order and print the Kth number. Array indexing starts from 0. Therefore, for K=1, you need to find the second smallest number.

Input

• First line: integer N (size of the array)
• Second line: an array consisting of N integers
• Third line: integer K (the rank of the number to find)

Output

Print the Kth number.

Example

Example 1

Input
5
3 1 2 5 4
2

Output
2
    

Example 2

Input
6
7 8 9 5 6 3
1

Output
3
    

Problem Analysis

To solve this problem, the array must be sorted. After sorting the array, you return the value located at the Kth index. The time complexity of sorting is O(N log N) with respect to the size of the array N. The time complexity for finding the Kth number afterward is very efficient at O(1).

Algorithm Approach

1. Receive the array as input.
2. Sort the array in ascending order.
3. Output the Kth number.

Implementation

Now, let’s write the Python code. Below is a simple code to solve this problem.

def find_kth_number(arr, k):
    # Sort the array in ascending order
    sorted_arr = sorted(arr)
    # Return the Kth number (since indexing starts from 0, we use k-1)
    return sorted_arr[k - 1]

# Input processing
N = int(input())
arr = list(map(int, input().split()))
K = int(input())

# Finding the Kth number
result = find_kth_number(arr, K)
print(result)
    

Code Explanation

The above code simply defines the function find_kth_number, receives an array, sorts it, and then returns the Kth number. k - 1 is used to adjust the index. It sequentially processes the size of the array, the elements of the array, and the value of K entered by the user.

Performance Analysis

This algorithm has a time complexity of O(N log N) and generally exhibits optimal performance utilizing Python’s built-in sorting algorithm, Timsort. It shows very fast performance when the data is not large or the K value is small.

Test Cases

The code produced can be validated against various test cases. Below are some additional test cases.

Test Case 1

Input
7
10 7 8 6 5 4 3
4

Output
6
    

Test Case 2

Input
8
20 30 10 40 50 5 2 1
3

Output
10
    

Conclusion

Through this course, we have learned how to solve the basic problem of finding the Kth number in an array. This problem often appears in coding tests and is very useful for understanding the basic concept of sorting and the usage of Python’s built-in functions. Solve a variety of problems to enhance your algorithm skills!