{"id":33952,"date":"2024-11-01T09:22:21","date_gmt":"2024-11-01T09:22:21","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=33952"},"modified":"2024-11-01T10:54:45","modified_gmt":"2024-11-01T10:54:45","slug":"c-coding-test-course-finding-the-k-th-number","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/33952\/","title":{"rendered":"C# Coding Test Course, Finding the K-th Number"},"content":{"rendered":"<article>\n<header>\n<p>This article provides a detailed explanation of the problem type &#8216;Finding the K-th number&#8217;, which is frequently tested in coding interviews, along with methods for solving it.<\/p>\n<\/header>\n<section>\n<h2>Problem Description<\/h2>\n<p>Given an array <code>arr<\/code> and an integer <code>K<\/code>, the task is to find and return the <code>K<\/code>-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.<\/p>\n<p>For example, if the array is <code>[7, 10, 4, 3, 20, 15]<\/code> and <code>K=3<\/code>, the 3rd smallest number is <code>7<\/code>.<\/p>\n<\/section>\n<section>\n<h2>Input Format<\/h2>\n<p>The input is given in the following format:<\/p>\n<ul>\n<li>First line: Size of the array <code>N<\/code> (<code>1 &lt;= N &lt;= 10^6<\/code>)<\/li>\n<li>Second line: <code>N<\/code> integers (elements of the array range from -10^9 to 10^9)<\/li>\n<li>Third line: An integer <code>K<\/code> (<code>1 &lt;= K &lt;= N<\/code>)<\/li>\n<\/ul>\n<\/section>\n<section>\n<h2>Input Example<\/h2>\n<pre><code>\n6\n7 10 4 3 20 15\n3\n        <\/code><\/pre>\n<\/section>\n<section>\n<h2>Output Format<\/h2>\n<p>The output should be the <code>K<\/code>-th smallest number in the array.<\/p>\n<\/section>\n<section>\n<h2>Output Example<\/h2>\n<pre><code>\n7\n        <\/code><\/pre>\n<\/section>\n<section>\n<h2>Solution Process<\/h2>\n<h3>Step 1: Understanding the Problem<\/h3>\n<p>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.<\/p>\n<h3>Step 2: Choosing the Algorithm<\/h3>\n<p>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:<\/p>\n<ul>\n<li>Quickselect algorithm (average O(N) time complexity)<\/li>\n<li>Using a heap data structure<\/li>\n<\/ul>\n<p>In this tutorial, we will be using the Quickselect method.<\/p>\n<h3>Step 3: Quickselect Explanation<\/h3>\n<p>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.<\/p>\n<h4>Process of Quickselect<\/h4>\n<ol>\n<li>Select a pivot value.<\/li>\n<li>Move values less than or equal to the pivot to the left and those greater to the right.<\/li>\n<li>If K is equal to the pivot index, return the pivot.<\/li>\n<li>If K is less than the pivot, recursively call Quickselect on the left part.<\/li>\n<li>If K is greater than the pivot, recursively call Quickselect on the right part.<\/li>\n<\/ol>\n<\/section>\n<section>\n<h2>C# Code Implementation<\/h2>\n<pre><code>\nusing System;\nusing System.Linq;\n\nclass KthSmallest\n{\n    public static int QuickSelect(int[] arr, int left, int right, int k)\n    {\n        if (left == right) \/\/ If the array has only one element\n            return arr[left];\n\n        Random random = new Random();\n        int pivotIndex = left + random.Next(right - left);\n        int pivot = arr[pivotIndex];\n\n        \/\/ Move pivot to the far right\n        Swap(arr, pivotIndex, right);\n        int storeIndex = left;\n\n        for (int i = left; i &lt; right; i++)\n        {\n            if (arr[i] &lt; pivot)\n            {\n                Swap(arr, storeIndex, i);\n                storeIndex++;\n            }\n        }\n\n        Swap(arr, storeIndex, right); \/\/ Place pivot in its correct position\n\n        if (k == storeIndex) return arr[k];\n        else if (k &lt; storeIndex) return QuickSelect(arr, left, storeIndex - 1, k);\n        else return QuickSelect(arr, storeIndex + 1, right, k);\n    }\n\n    private static void Swap(int[] arr, int i, int j)\n    {\n        int temp = arr[i];\n        arr[i] = arr[j];\n        arr[j] = temp;\n    }\n\n    static void Main()\n    {\n        int N = int.Parse(Console.ReadLine());\n        int[] arr = Console.ReadLine().Split().Select(int.Parse).ToArray();\n        int K = int.Parse(Console.ReadLine()) - 1; \/\/ Convert K to a 0-based index\n\n        int result = QuickSelect(arr, 0, N - 1, K);\n        Console.WriteLine(result);\n    }\n}\n        <\/code><\/pre>\n<\/section>\n<section>\n<h2>Code Explanation<\/h2>\n<p>The above C# code uses the Quickselect algorithm to find the K-th number:<\/p>\n<ul>\n<li><code>QuickSelect<\/code> method: Finds and returns the K-th smallest number in the array.<\/li>\n<li><code>Swap<\/code> method: Swaps the positions of two elements.<\/li>\n<li><code>Main<\/code>: Receives input and executes the program.<\/li>\n<\/ul>\n<p>This algorithm has an average time complexity of O(N), which is very efficient.<\/p>\n<\/section>\n<section>\n<h2>Conclusion<\/h2>\n<p>In this tutorial, we learned how to solve the &#8216;Finding the K-th number&#8217; 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.<\/p>\n<\/section>\n<\/article>\n","protected":false},"excerpt":{"rendered":"<p>This article provides a detailed explanation of the problem type &#8216;Finding the K-th number&#8217;, which is frequently tested in coding interviews, along with methods for solving it. 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 &hellip; <a href=\"https:\/\/atmokpo.com\/w\/33952\/\" class=\"more-link\">\ub354 \ubcf4\uae30<span class=\"screen-reader-text\"> &#8220;C# Coding Test Course, Finding the K-th Number&#8221;<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[90],"tags":[],"class_list":["post-33952","post","type-post","status-publish","format-standard","hentry","category-c-coding-test-tutorials"],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v26.2 - https:\/\/yoast.com\/wordpress\/plugins\/seo\/ -->\n<title>C# Coding Test Course, Finding the K-th Number - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/atmokpo.com\/w\/33952\/\" \/>\n<meta property=\"og:locale\" content=\"ko_KR\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"C# Coding Test Course, Finding the K-th Number - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"og:description\" content=\"This article provides a detailed explanation of the problem type &#8216;Finding the K-th number&#8217;, which is frequently tested in coding interviews, along with methods for solving it. 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 &hellip; \ub354 \ubcf4\uae30 &quot;C# Coding Test Course, Finding the K-th Number&quot;\" \/>\n<meta property=\"og:url\" content=\"https:\/\/atmokpo.com\/w\/33952\/\" \/>\n<meta property=\"og:site_name\" content=\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"article:published_time\" content=\"2024-11-01T09:22:21+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2024-11-01T10:54:45+00:00\" \/>\n<meta name=\"author\" content=\"root\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:creator\" content=\"@bebubo4\" \/>\n<meta name=\"twitter:site\" content=\"@bebubo4\" \/>\n<meta name=\"twitter:label1\" content=\"\uae00\uc4f4\uc774\" \/>\n\t<meta name=\"twitter:data1\" content=\"root\" \/>\n\t<meta name=\"twitter:label2\" content=\"\uc608\uc0c1 \ub418\ub294 \ud310\ub3c5 \uc2dc\uac04\" \/>\n\t<meta name=\"twitter:data2\" content=\"3\ubd84\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\/\/atmokpo.com\/w\/33952\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/33952\/\"},\"author\":{\"name\":\"root\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7\"},\"headline\":\"C# Coding Test Course, Finding the K-th Number\",\"datePublished\":\"2024-11-01T09:22:21+00:00\",\"dateModified\":\"2024-11-01T10:54:45+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/atmokpo.com\/w\/33952\/\"},\"wordCount\":437,\"publisher\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\"},\"articleSection\":[\"C# Coding Test Tutorials\"],\"inLanguage\":\"ko-KR\"},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/atmokpo.com\/w\/33952\/\",\"url\":\"https:\/\/atmokpo.com\/w\/33952\/\",\"name\":\"C# Coding Test Course, Finding the K-th Number - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#website\"},\"datePublished\":\"2024-11-01T09:22:21+00:00\",\"dateModified\":\"2024-11-01T10:54:45+00:00\",\"breadcrumb\":{\"@id\":\"https:\/\/atmokpo.com\/w\/33952\/#breadcrumb\"},\"inLanguage\":\"ko-KR\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/atmokpo.com\/w\/33952\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/atmokpo.com\/w\/33952\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"\ud648\",\"item\":\"https:\/\/atmokpo.com\/w\/en\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"C# Coding Test Course, Finding the K-th Number\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/atmokpo.com\/w\/#website\",\"url\":\"https:\/\/atmokpo.com\/w\/\",\"name\":\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\",\"description\":\"\",\"publisher\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\"},\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/atmokpo.com\/w\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"ko-KR\"},{\"@type\":\"Organization\",\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\",\"name\":\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\",\"url\":\"https:\/\/atmokpo.com\/w\/\",\"logo\":{\"@type\":\"ImageObject\",\"inLanguage\":\"ko-KR\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/logo\/image\/\",\"url\":\"https:\/\/atmokpo.com\/w\/wp-content\/uploads\/2024\/11\/logo.png\",\"contentUrl\":\"https:\/\/atmokpo.com\/w\/wp-content\/uploads\/2024\/11\/logo.png\",\"width\":400,\"height\":400,\"caption\":\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\"},\"image\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/logo\/image\/\"},\"sameAs\":[\"https:\/\/x.com\/bebubo4\"]},{\"@type\":\"Person\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7\",\"name\":\"root\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"ko-KR\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/secure.gravatar.com\/avatar\/708197b41fc6435a7ce22d951b25d4a47e9e904270cb1f04682d4f025066f80c?s=96&d=mm&r=g\",\"contentUrl\":\"https:\/\/secure.gravatar.com\/avatar\/708197b41fc6435a7ce22d951b25d4a47e9e904270cb1f04682d4f025066f80c?s=96&d=mm&r=g\",\"caption\":\"root\"},\"sameAs\":[\"http:\/\/atmokpo.com\/w\"],\"url\":\"https:\/\/atmokpo.com\/w\/author\/root\/\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"C# Coding Test Course, Finding the K-th Number - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/atmokpo.com\/w\/33952\/","og_locale":"ko_KR","og_type":"article","og_title":"C# Coding Test Course, Finding the K-th Number - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","og_description":"This article provides a detailed explanation of the problem type &#8216;Finding the K-th number&#8217;, which is frequently tested in coding interviews, along with methods for solving it. 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 &hellip; \ub354 \ubcf4\uae30 \"C# Coding Test Course, Finding the K-th Number\"","og_url":"https:\/\/atmokpo.com\/w\/33952\/","og_site_name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","article_published_time":"2024-11-01T09:22:21+00:00","article_modified_time":"2024-11-01T10:54:45+00:00","author":"root","twitter_card":"summary_large_image","twitter_creator":"@bebubo4","twitter_site":"@bebubo4","twitter_misc":{"\uae00\uc4f4\uc774":"root","\uc608\uc0c1 \ub418\ub294 \ud310\ub3c5 \uc2dc\uac04":"3\ubd84"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/atmokpo.com\/w\/33952\/#article","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/33952\/"},"author":{"name":"root","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7"},"headline":"C# Coding Test Course, Finding the K-th Number","datePublished":"2024-11-01T09:22:21+00:00","dateModified":"2024-11-01T10:54:45+00:00","mainEntityOfPage":{"@id":"https:\/\/atmokpo.com\/w\/33952\/"},"wordCount":437,"publisher":{"@id":"https:\/\/atmokpo.com\/w\/#organization"},"articleSection":["C# Coding Test Tutorials"],"inLanguage":"ko-KR"},{"@type":"WebPage","@id":"https:\/\/atmokpo.com\/w\/33952\/","url":"https:\/\/atmokpo.com\/w\/33952\/","name":"C# Coding Test Course, Finding the K-th Number - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/#website"},"datePublished":"2024-11-01T09:22:21+00:00","dateModified":"2024-11-01T10:54:45+00:00","breadcrumb":{"@id":"https:\/\/atmokpo.com\/w\/33952\/#breadcrumb"},"inLanguage":"ko-KR","potentialAction":[{"@type":"ReadAction","target":["https:\/\/atmokpo.com\/w\/33952\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/atmokpo.com\/w\/33952\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"\ud648","item":"https:\/\/atmokpo.com\/w\/en\/"},{"@type":"ListItem","position":2,"name":"C# Coding Test Course, Finding the K-th Number"}]},{"@type":"WebSite","@id":"https:\/\/atmokpo.com\/w\/#website","url":"https:\/\/atmokpo.com\/w\/","name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","description":"","publisher":{"@id":"https:\/\/atmokpo.com\/w\/#organization"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/atmokpo.com\/w\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"ko-KR"},{"@type":"Organization","@id":"https:\/\/atmokpo.com\/w\/#organization","name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","url":"https:\/\/atmokpo.com\/w\/","logo":{"@type":"ImageObject","inLanguage":"ko-KR","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/logo\/image\/","url":"https:\/\/atmokpo.com\/w\/wp-content\/uploads\/2024\/11\/logo.png","contentUrl":"https:\/\/atmokpo.com\/w\/wp-content\/uploads\/2024\/11\/logo.png","width":400,"height":400,"caption":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8"},"image":{"@id":"https:\/\/atmokpo.com\/w\/#\/schema\/logo\/image\/"},"sameAs":["https:\/\/x.com\/bebubo4"]},{"@type":"Person","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7","name":"root","image":{"@type":"ImageObject","inLanguage":"ko-KR","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/image\/","url":"https:\/\/secure.gravatar.com\/avatar\/708197b41fc6435a7ce22d951b25d4a47e9e904270cb1f04682d4f025066f80c?s=96&d=mm&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/708197b41fc6435a7ce22d951b25d4a47e9e904270cb1f04682d4f025066f80c?s=96&d=mm&r=g","caption":"root"},"sameAs":["http:\/\/atmokpo.com\/w"],"url":"https:\/\/atmokpo.com\/w\/author\/root\/"}]}},"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack-related-posts":[],"_links":{"self":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/33952","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/comments?post=33952"}],"version-history":[{"count":1,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/33952\/revisions"}],"predecessor-version":[{"id":33953,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/33952\/revisions\/33953"}],"wp:attachment":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/media?parent=33952"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/categories?post=33952"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/tags?post=33952"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}