{"id":1313,"date":"2024-01-04T13:00:00","date_gmt":"2024-01-04T13:00:00","guid":{"rendered":"https:\/\/favtutor.com\/articles\/?p=1313"},"modified":"2024-01-08T09:35:47","modified_gmt":"2024-01-08T09:35:47","slug":"find-the-duplicate-number","status":"publish","type":"post","link":"https:\/\/favtutor.com\/articles\/find-the-duplicate-number\/","title":{"rendered":"Find the Duplicate Number Problem (C++, Java, Python)"},"content":{"rendered":"\n<p>The array contains a lot of problems in the world of programming. One of the most interesting challenges is the identification of repeated numbers within an array. This article will discuss different approaches to finding the duplicate number present and implementing their code in C++, Java, and Python.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>What is the Find the Duplicate Number Problem?<\/strong><\/h2>\n\n\n\n<p><strong>In the Find the Duplicate Number problem, we are given an array of integer nums containing n + 1 integers where each integer is inclusive in the range [1, n]. <\/strong>The array contains a duplicate number and our task is to return that duplicate number.<\/p>\n\n\n\n<p><strong>Input:<\/strong> nums = [1, 4, 3, 2, 2]<\/p>\n\n\n\n<p><strong>Output:<\/strong> 2<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Brute Force Approach: Using Sorting<\/strong><\/h2>\n\n\n\n<p>First, we will try to use the brute force approach, where we will use sorting to find the duplicate number. The initial step in this approach involves sorting the array in ascending order. After sorting duplicates numbers are adjacent to each other. So now we will simply compare the adjacent number using a loop.<\/p>\n\n\n\n<p>Here are the steps involved in this approach:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Sorting<\/strong>: first of all we will sort our array in ascending order using an inbuilt sort function<\/li>\n<\/ul>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter\"><img decoding=\"async\" src=\"https:\/\/lh7-us.googleusercontent.com\/TBHPq_Z4Hns9RLxh25J9_9OZGG7BUU16WC4Vb8KkE6A4OdWTmGbvAEX4Pv23Qt6GMur8U_DnNROLQtqKAbjTnEhGGseyt9dM8aGLu208wMinIZ1cqPYqBGAFckCxEuynaDbuk6Nw1-w87MyjZAg3LIc\" alt=\"sort the array in ascending order\"\/><\/figure>\n<\/div>\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Adjacent Comparison<\/strong>: After sorting the detection of duplicates becomes straightforward. By iterating through the array, a simple check of whether <strong>arr[i] is equal to arr[i+1] <\/strong>will tell us about the duplicate number.<\/li>\n<\/ul>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/lh7-us.googleusercontent.com\/tMacPUYDnU8BJCRhE_EYjclmsSZvFBIzI8mOC0i4vvpBqm_m00ZIDeoIeIC3ZGpZ3AmLWbPYAidl3UBneZOqcMcKU7ZF30w2V8bZR70kRorZdGrRdiiluHz_8jGCDYNI1Ptb68BRWYlCBEj90vDOIkc\" alt=\"Adjacent Comparison\"\/><\/figure>\n\n\n\n<p>The Time complexity is O(Nlogn + N) for this approach NlogN for sorting the array and O(N) for traversing through the array and checking if adjacent elements are equal. The Space complexity is O(1) as we are not using any extra space.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Better Approach: Using a Frequency Array<\/strong><\/h2>\n\n\n\n<p>In this approach, we will create a frequency array of size N+1. and now we will set all elements of the frequency array to 0. The following are the steps used in this approach:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Now we will iterate through each element in the given array. Check the corresponding index in the frequency array.<\/li>\n\n\n\n<li>Now if the frequency of the element is 0 we will increase it by 1, else if the frequency is not 0 then that element is the duplicate element.<\/li>\n<\/ul>\n\n\n\n<p>The time complexity is O(N) as we traverse through the array only once. The space complexity is O(N) as we use extra space for the frequency array.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Optimal Approach: Using Linked List Cycle<\/strong><\/h2>\n\n\n\n<p><strong>If there is a duplicate number we can always say that a cycle will be formed. This approach utilizes Floyd&#8217;s Tortoise and Hare algorithm commonly used for cycle detection in linked lists.\u00a0 In a cycle, the distance traveled by the fast pointer is twice that of the slow pointer<\/strong>.<\/p>\n\n\n\n<p>If you don&#8217;t know much about Floyd&#8217;s Tortoise and Hare algorithm, you can learn more about <a href=\"https:\/\/favtutor.com\/articles\/detect-linked-list-cycle\/\" data-type=\"link\" data-id=\"https:\/\/favtutor.com\/articles\/detect-linked-list-cycle\/\">linked list cycle detection<\/a>.<\/p>\n\n\n\n<p>Following are the steps involved in finding the duplicate number using the linked list cycle:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Initially, we have 1, then we got to the first index, we have 4,<\/li>\n\n\n\n<li>we go to the 4th index, we have 2,&nbsp;<\/li>\n\n\n\n<li>we go to the 2nd index, we have 3,&nbsp;<\/li>\n\n\n\n<li>we go to the 3rd index, we get 2 again, and here the cycle is formed.<\/li>\n<\/ul>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/lh7-us.googleusercontent.com\/stfbrSZ1ACF-z7p8B3qudO7Wh7Es3nCPvKH-pHE9sRwv9LfmNWNPoGcOBn-2Lob3YbD4p7RvLaQPNJU8FSRdzFgKwDNOQI5GH0tpexG8swLhZje0dz_cIEH6YjJ7xlfelgpMgQ-lg3QN1n_x5R4e2ks\" alt=\"cycle is formed\"\/><\/figure>\n\n\n\n<ul class=\"wp-block-list\">\n<li>We will consider each index in the array as a node in a linked list and initialize two pointers, slow and fast, both pointing to the first element of the array.<\/li>\n<\/ul>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/lh7-us.googleusercontent.com\/3y9aw3QhdzZl9t_VYjJlfkse_w8zD-xQlvi0xUyysaA78ho1ZqK3vE7M0D9V1Bs_IyrBkyEQiIAv0hSw974MTMm9eoW7CnbqiM9yjMzuTfLsCmu6QV0ZAsfIaMUZfhY_R0lr9ZTuTVkGv4Y9n7drhLY\" alt=\"initialize two pointers, slow and fast\"\/><\/figure>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Now we will use a loop to move the slow pointer one step at a time and the fast pointer two steps at a time.<\/li>\n<\/ul>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/lh7-us.googleusercontent.com\/y-0vEJLrUIR0vwUQBsdw-ndvwsNI56O5ZC2pR8SI45Tj3AuyXfeGVkrqBgURnZlgZV8BNq-CgfNAZC6MefGrShXjKGM1ZXmLl2iAoUuowm3kbzjiWrnIJBZ_05kYEjs8-RnaVMyptIOH9qBo0KvQ8nk\" alt=\"Move the slow and fast pointers\"\/><\/figure>\n\n\n\n<ul class=\"wp-block-list\">\n<li>If there is a duplicate in the array, the pointers will eventually meet at the same index, forming a cycle.<\/li>\n<\/ul>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/lh7-us.googleusercontent.com\/gif4X6yQ6eUukPh5lnAjsUEiRDynKGoCM2SX_JZQIutPpaX_ocqQVFFTjff2TtsL3J0IO3NcyM7bCKPTiUUf6Phh93qtQsnhdWTfBKnRcDZ6PI3kRPJicnaMAZUXTxm1OJ3TlfeeDOLOC05deLfMWfc\" alt=\"Pointer meets\"\/><\/figure>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Once the slow and fast pointers meet, reset one of the pointers (let&#8217;s say slow) to the first element<\/li>\n<\/ul>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/lh7-us.googleusercontent.com\/YpMfDONuSt8iDkePQ9EAG6hekm3mG3JdGp2nWT3piTvFtG5t10zFDFrUwemW5Ikpd648YkctRwa-YiKYM7SjBfwnCx8V8scmcdxnSlxkaf1_MNYZIFIxhA_k11kMj74fYe0MmtJj2X9L6eBWQjLelk0\" alt=\"reset the slow pointer\"\/><\/figure>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Now we will move both pointers one step at a time until they meet again. The meeting point is the entrance to the cycle<\/li>\n<\/ul>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/lh7-us.googleusercontent.com\/1NDUJdoPyJPQ7qYVnXzaPuozCwiJJXbEcjgdeNU8MqXHSB52hdseZK06tqHblaFp3MsdMWfx31lTJS_T-McXkoeKRaxwi0YQaCudK81C9K5kbeCjdmU71RecZQ0aWfeEORmAMX5-a49NyH1w8a5BHr4\" alt=\"Move one step each\"\/><\/figure>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/lh7-us.googleusercontent.com\/q_nB8yazoT_wCuwZ-IVy8WsOloQgcDFAK7QSwuwZ6y745QSdz902H0jg6vZeCCNLLvDV19fXG4CRkPSpuNljEepK_CrgCsML8i6TYY6RLh1i-FOOsb93e67HWKJKZUJjC_KIrIjNmyZFU_en4TDGkwM\" alt=\"Pointers meet\"\/><\/figure>\n\n\n\n<ul class=\"wp-block-list\">\n<li>The element at the entrance to the cycle is the duplicate number in the array.<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\"><strong>C++ Code<\/strong><\/h3>\n\n\n\n<p>We provided the C++ program to find the duplicate number:<\/p>\n\n\n\n<div class=\"wp-block-codemirror-blocks-code-block code-block\"><pre class=\"CodeMirror\" data-setting=\"{&quot;mode&quot;:&quot;clike&quot;,&quot;mime&quot;:&quot;text\/x-c++src&quot;,&quot;theme&quot;:&quot;material&quot;,&quot;lineNumbers&quot;:true,&quot;styleActiveLine&quot;:false,&quot;lineWrapping&quot;:false,&quot;readOnly&quot;:true,&quot;language&quot;:&quot;C++&quot;,&quot;modeName&quot;:&quot;cpp&quot;}\">#include &lt;bits\/stdc++.h&gt;\n\nusing namespace std;\n\n\/\/ Function to find the duplicate number in an array using linked list cycle detection\nint findDuplicate(vector&lt;int&gt; &amp;nums) {\n    int slow = nums[0];\n    int fast = nums[0];\n\n    \/\/ Phase 1: Detect the intersection point in the cycle\n    do {\n        slow = nums[slow];\n        fast = nums[nums[fast]];\n    } while (slow != fast);\n\n    \/\/ Phase 2: Find the entrance to the cycle\n    slow = nums[0];\n    while (slow != fast) {\n        slow = nums[slow];\n        fast = nums[fast];\n    }\n\n    \/\/ The duplicate element is found at the entrance to the cycle\n    return slow;\n}\n\nint main() {\n    \/\/ Example usage with the array [1, 4, 3, 2, 2]\n    vector&lt;int&gt; nums = {1, 4, 3, 2, 2};\n    \n    \/\/ Call the findDuplicate function and display the result\n    cout &lt;&lt; &quot;The duplicate element is &quot; &lt;&lt; findDuplicate(nums) &lt;&lt; endl;\n\n    return 0;\n}<\/pre><\/div>\n\n\n\n<h3 class=\"wp-block-heading\"><strong>Java Code<\/strong><\/h3>\n\n\n\n<p>Here is the Java program for this leetcode problem:<\/p>\n\n\n\n<div class=\"wp-block-codemirror-blocks-code-block code-block\"><pre class=\"CodeMirror\" data-setting=\"{&quot;mode&quot;:&quot;clike&quot;,&quot;mime&quot;:&quot;text\/x-java&quot;,&quot;theme&quot;:&quot;material&quot;,&quot;lineNumbers&quot;:true,&quot;styleActiveLine&quot;:false,&quot;lineWrapping&quot;:false,&quot;readOnly&quot;:true,&quot;language&quot;:&quot;Java&quot;,&quot;modeName&quot;:&quot;java&quot;}\">import java.util.Arrays;\n\npublic class FindDuplicate {\n\n    \/\/ Function to find the duplicate number in an array using linked list cycle detection\n    public static int findDuplicate(int[] nums) {\n        int slow = nums[0];\n        int fast = nums[0];\n\n        \/\/ Phase 1: Detect the intersection point in the cycle\n        do {\n            slow = nums[slow];\n            fast = nums[nums[fast]];\n        } while (slow != fast);\n\n        \/\/ Phase 2: Find the entrance to the cycle\n        slow = nums[0];\n        while (slow != fast) {\n            slow = nums[slow];\n            fast = nums[fast];\n        }\n\n        \/\/ The duplicate element is found at the entrance to the cycle\n        return slow;\n    }\n\n    public static void main(String[] args) {\n        \/\/ Example usage with the array [1, 4, 3, 2, 2]\n        int[] nums = {1, 4, 3, 2, 2};\n        \n        \/\/ Call the findDuplicate function and display the result\n        System.out.println(&quot;The duplicate element is &quot; + findDuplicate(nums));\n    }\n}<\/pre><\/div>\n\n\n\n<h3 class=\"wp-block-heading\"><strong>Python Code<\/strong><\/h3>\n\n\n\n<p>You can implement it in Python as well:<\/p>\n\n\n\n<div class=\"wp-block-codemirror-blocks-code-block code-block\"><pre class=\"CodeMirror\" data-setting=\"{&quot;mode&quot;:&quot;python&quot;,&quot;mime&quot;:&quot;text\/x-python&quot;,&quot;theme&quot;:&quot;material&quot;,&quot;lineNumbers&quot;:true,&quot;styleActiveLine&quot;:false,&quot;lineWrapping&quot;:false,&quot;readOnly&quot;:true,&quot;language&quot;:&quot;Python&quot;,&quot;modeName&quot;:&quot;python&quot;}\">def findDuplicate(nums):\n    slow = nums[0]\n    fast = nums[0]\n\n    # Phase 1: Detect the intersection point in the cycle\n    while True:\n        slow = nums[slow]\n        fast = nums[nums[fast]]\n        if slow == fast:\n            break\n\n    # Phase 2: Find the entrance to the cycle\n    slow = nums[0]\n    while slow != fast:\n        slow = nums[slow]\n        fast = nums[fast]\n\n    # The duplicate element is found at the entrance to the cycle\n    return slow\n\n# Example usage with the array [1, 4, 3, 2, 2]\nnums = [1, 4, 3, 2, 2]\nprint(&quot;The duplicate element is&quot;, findDuplicate(nums))<\/pre><\/div>\n\n\n\n<p><strong>Output:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-code has-black-color has-text-color has-background\" style=\"background-color:#fedcba\"><code>The duplicate element is 2<\/code><\/pre>\n\n\n\n<p>The time complexity is O(N) as we traverse through the array only once. The space complexity of this approach is O(1) as we haven\u2019t used any extra space.<\/p>\n\n\n\n<p>In the end, let&#8217;s do a comparative analysis of all the methods:<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table><tbody><tr><td><strong>Approach&nbsp;<\/strong><\/td><td><strong>Time complexity<\/strong><\/td><td><strong>Space complexity<\/strong><\/td><td><strong>Details&nbsp;<\/strong><\/td><\/tr><tr><td>Sorting Approach<\/td><td>O(Nlogn + N)<\/td><td>O(1)<\/td><td>NlogN for sorting the array and O(N) for traversing through the array and checking if adjacent elements are equal.<\/td><\/tr><tr><td>Frequency Approach<\/td><td>O(N)<\/td><td>O(N)<\/td><td>As we are traversing through the array only once.<\/td><\/tr><tr><td>Linked List Cycle Approach<\/td><td>O(N)<\/td><td>O(1)<\/td><td>As we are traversing through the array only once.<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Conclusion<\/strong><\/h2>\n\n\n\n<p>In conclusion, we explored three approaches to solve this <a href=\"https:\/\/leetcode.com\/problems\/find-the-duplicate-number\/\" target=\"_blank\" data-type=\"link\" data-id=\"https:\/\/leetcode.com\/problems\/find-the-duplicate-number\/\" rel=\"noreferrer noopener nofollow\">leetcode problem<\/a> of identifying the duplicate number in an array: the Sorting Approach, the Frequency Approach, and the optimal Linked List Cycle Detection. The Linked List Cycle Detection stands out with linear time complexity and minimal space usage, making it the optimal choice. <\/p>\n","protected":false},"excerpt":{"rendered":"<p>Let&#8217;s solve the leetcode problem to find the duplicate number, using sorting, frequency array, and linked list cycle.<\/p>\n","protected":false},"author":12,"featured_media":1316,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"jnews-multi-image_gallery":[],"jnews_single_post":null,"jnews_primary_category":{"id":"","hide":""},"footnotes":""},"categories":[7],"tags":[14,15],"class_list":["post-1313","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-data-structures-algorithms","tag-dsa","tag-leetcode"],"_links":{"self":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/1313","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/users\/12"}],"replies":[{"embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/comments?post=1313"}],"version-history":[{"count":3,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/1313\/revisions"}],"predecessor-version":[{"id":1347,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/1313\/revisions\/1347"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/media\/1316"}],"wp:attachment":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/media?parent=1313"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/categories?post=1313"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/tags?post=1313"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}