{"id":1051,"date":"2023-12-16T21:00:00","date_gmt":"2023-12-16T21:00:00","guid":{"rendered":"https:\/\/favtutor.com\/articles\/?p=1051"},"modified":"2023-12-18T05:35:29","modified_gmt":"2023-12-18T05:35:29","slug":"find-the-missing-number","status":"publish","type":"post","link":"https:\/\/favtutor.com\/articles\/find-the-missing-number\/","title":{"rendered":"Find the Missing Number (C++, Java, Python)"},"content":{"rendered":"\n<p>There are many simple technical interview questions with arrays, including finding the missing number. This programming problem incorporates concepts from mathematics, and bit manipulation, and can be solved using hashing and linear search. In this article, we will explore various approaches to solving the Missing Number problem.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>What is the Find the Missing Number Problem?<\/strong><\/h2>\n\n\n\n<p><strong>In the Missing Number problem, we have an array of integers containing numbers in a specific range [0 to n], with one number missing from the sequence.<\/strong> Our task is to identify and return the missing number.\u00a0<br>Let us understand it better with an example:<\/p>\n\n\n\n<p class=\"has-black-color has-text-color has-background\" style=\"background-color:#fedcba\"><strong>Nums <\/strong>= [2,0,1,4,5]<br><strong>Output <\/strong>= 3<\/p>\n\n\n\n<p>The above array contains all the numbers from 0 to 5 except 3.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Brute Force Approach<\/strong><\/h2>\n\n\n\n<p>Using the simple Brute Force approach, we will try to find every number from 0 to n in the given nums array using linear search and if we are unable to find any number in our array then that number is our missing number.<\/p>\n\n\n\n<p>We will run a nested loop outer loop from 0 to n in our given range:<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li>For each integer i, we will try to find it in the given array using linear search.<\/li>\n\n\n\n<li>In the inner loop, we will iterate over the array and consider a bool variable that will tell if the element is present in the array or not firstly we will set the bool to false, and if we will set the bool value to true.<\/li>\n\n\n\n<li>And if we find a number in the inner array we will break from the inner loop and check for another number.<\/li>\n\n\n\n<li>After every iteration, we will check our bool if it is false then we will return our number I which is our missing number.<\/li>\n\n\n\n<li><\/li>\n<\/ol>\n\n\n\n<p>The time complexity of this approach is O(N<sup>2<\/sup>), because in the worst case if the missing number is N itself, the outer loop will run N times, and for every number the inner loop will also run for approximately N times. The space complexity O(1) as we are not using any extra space.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Using Hashing\u00a0to Find the Missing Number<\/strong><\/h2>\n\n\n\n<p><strong>In the Hashing approach to find the missing number, we will use a hash array of size n+1 to store the count of each number. Then we will check the number that is not present.\u00a0<\/strong><\/p>\n\n\n\n<p>Let\u2019s say, Nums = [2,0,1,4,5] and N = 5.<\/p>\n\n\n\n<p>Initializing the hash array:<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large\"><img decoding=\"async\" width=\"1024\" height=\"219\" src=\"https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/1-11-1024x219.png\" alt=\"Initializing the hash array\" class=\"wp-image-1055\" srcset=\"https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/1-11-1024x219.png 1024w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/1-11-300x64.png 300w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/1-11-768x164.png 768w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/1-11-750x161.png 750w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/1-11-1140x244.png 1140w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/1-11.png 1280w\" sizes=\"(max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n<\/div>\n\n\n<p>Below are the steps to follow for the hashing approach:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>For every element present in the array we will mark that position as 1 in our hash array because we know that our element is in the range of 0 to N so every index of the hash array represents a number.<\/li>\n\n\n\n<li>For example, at the 0th index, we have 2 in our nums array. So we will mark the 2nd index as 1.&nbsp;<\/li>\n<\/ul>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large\"><img decoding=\"async\" width=\"1024\" height=\"203\" src=\"https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/2-1-1-1024x203.png\" alt=\"0th index\" class=\"wp-image-1056\" srcset=\"https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/2-1-1-1024x203.png 1024w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/2-1-1-300x60.png 300w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/2-1-1-768x153.png 768w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/2-1-1-750x149.png 750w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/2-1-1-1140x226.png 1140w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/2-1-1.png 1279w\" sizes=\"(max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n<\/div>\n\n\n<ul class=\"wp-block-list\">\n<li>Similarly, After marking our hash array for every number present in the nums array our hash array will look like this.<\/li>\n<\/ul>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large\"><img decoding=\"async\" width=\"1024\" height=\"197\" src=\"https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/3-10-1024x197.png\" alt=\"After marking hash array for every number \" class=\"wp-image-1057\" srcset=\"https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/3-10-1024x197.png 1024w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/3-10-300x58.png 300w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/3-10-768x148.png 768w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/3-10-750x144.png 750w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/3-10-1140x219.png 1140w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/3-10.png 1280w\" sizes=\"(max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n<\/div>\n\n\n<ul class=\"wp-block-list\">\n<li>After marking the hash array for all numbers present in the nums array we will iterate in our hash array and return that index to the hash array where the number is 0.<\/li>\n<\/ul>\n\n\n\n<p>The time complexity of this approach is O(2*N), O(N) for storing frequencies in the hash array, and O(N) for checking the number with 0 frequency in the hash array.\u00a0<\/p>\n\n\n\n<p>The space complexity is O(N) where N is the size of array+1. Because we are using an additional hash array. Learn more about <a href=\"https:\/\/favtutor.com\/blogs\/hashing-in-data-structure\" data-type=\"link\" data-id=\"https:\/\/favtutor.com\/blogs\/hashing-in-data-structure\">hashing in data structures<\/a> here.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Optimized approach using XOR Operator<\/strong><\/h2>\n\n\n\n<p>We know that the XOR<strong> <\/strong>of two numbers is 0 so we can find the missing number using this XOR operator. We will run a loop and calculate the value of XOR of all the elements of the array. Then, if we again XOR this with numbers from 0 to n, the numbers that are already present nullify the effect and what is remaining is our missing number.<\/p>\n\n\n\n<p>Here is how to do it step-by-step:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>In this approach, we will declare two variables with names xor1 and xor2.<\/li>\n\n\n\n<li>In xor1 we will do bitwise xor of nums array and in xor2 we will do bitwise xor of number from 0 to n using a for loop.<\/li>\n\n\n\n<li>At last, we will do bitwise xor of xor1 and xor2 and we will get our missing number<\/li>\n\n\n\n<li>The same number xor gives 0 and one number that is missing will be left at the last<\/li>\n<\/ul>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large\"><img decoding=\"async\" width=\"1024\" height=\"247\" src=\"https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/4-8-1024x247.png\" alt=\"Optimized approach using XOR Operator\" class=\"wp-image-1058\" srcset=\"https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/4-8-1024x247.png 1024w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/4-8-300x72.png 300w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/4-8-768x185.png 768w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/4-8-750x181.png 750w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/4-8-1140x275.png 1140w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/4-8.png 1279w\" sizes=\"(max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n<\/div>\n\n\n<ul class=\"wp-block-list\">\n<li>From this xor1^xor2 we will get our missing number 3.<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\"><strong>C++ Code<\/strong><\/h3>\n\n\n\n<p>Here is the C++ program to find the missing 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;iostream&gt;\n#include &lt;vector&gt;\n\nusing namespace std;\n\nint missingNumber(vector&lt;int&gt;&amp; nums) {\n    int n = nums.size();\n    \n    \/\/ Initialize XOR results\n    int xor1 = 0;\n    int xor2 = 0;\n\n    \/\/ Calculate XOR of expected values (0 to n) and actual values in the array\n    for (int i = 0; i &lt;= n; ++i) {\n        xor1 ^= i;\n\n        \/\/ XOR each element in the array\n        if (i &lt; n) {\n            xor2 ^= nums[i];\n        }\n    }\n\n    \/\/ XOR result will be the missing number\n    return xor1 ^ xor2;\n}\n\nint main() {\n    \/\/ Example usage\n    vector&lt;int&gt; nums = {2, 0, 1, 4, 5};\n\n    int result = missingNumber(nums);\n\n    cout &lt;&lt; &quot;The missing number is: &quot; &lt;&lt; result &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 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;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;}\">public class MissingNumber {\n    public static int missingNumber(int[] nums) {\n        int n = nums.length;\n        \n        \/\/ Initialize XOR results\n        int xor1 = 0;\n        int xor2 = 0;\n\n        \/\/ Calculate XOR of expected values (0 to n) and actual values in the array\n        for (int i = 0; i &lt;= n; ++i) {\n            xor1 ^= i;\n\n            \/\/ XOR each element in the array\n            if (i &lt; n) {\n                xor2 ^= nums[i];\n            }\n        }\n\n        \/\/ XOR result will be the missing number\n        return xor1 ^ xor2;\n    }\n\n    public static void main(String[] args) {\n        \/\/ Example usage\n        int[] nums = {2, 0, 1, 4, 5};\n\n        int result = missingNumber(nums);\n\n        System.out.println(&quot;The missing number is: &quot; + result);\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 do the same with 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 missingNumber(nums):\n    n = len(nums)\n    \n    # Initialize XOR results\n    xor1 = 0\n    xor2 = 0\n\n    # Calculate XOR of expected values (0 to n) and actual values in the array\n    for i in range(n + 1):\n        xor1 ^= i\n\n        # XOR each element in the array\n        if i &lt; n:\n            xor2 ^= nums[i]\n\n    # XOR result will be the missing number\n    return xor1 ^ xor2\n\n# Example usage\nnums = [2, 0, 1, 4, 5]\nresult = missingNumber(nums)\n\nprint(&quot;The missing number is:&quot;, result)<\/pre><\/div>\n\n\n\n<p>The time complexity of this approach is O(N) where n is the size of the nums array. Since we are iterating till N two times, we will get linear complexity. The space complexity is O(1) as we are not using any extra space.<\/p>\n\n\n\n<p>Now you have 3 methods, let&#8217;s do a small comparative analysis of all of them to find the best one for different situations:<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table><tbody><tr><td><strong>Approaches<\/strong><\/td><td class=\"has-text-align-center\" data-align=\"center\"><strong>Time complexity<\/strong><\/td><td class=\"has-text-align-center\" data-align=\"center\"><strong>Space complexity<\/strong><\/td><td><strong>Details<\/strong><\/td><\/tr><tr><td>Brute force<\/td><td class=\"has-text-align-center\" data-align=\"center\">O(N<sup>2<\/sup>)<\/td><td class=\"has-text-align-center\" data-align=\"center\">O(1)<\/td><td>In the worst case if the missing number is N itself, the outer loop will run N times, and for every number the inner loop will also run for approximately N times.<\/td><\/tr><tr><td>Hashing&nbsp;<\/td><td class=\"has-text-align-center\" data-align=\"center\">O(2*N)<\/td><td class=\"has-text-align-center\" data-align=\"center\">O(N)<\/td><td>O(N) for storing frequencies in the hash array, and O(N) for checking the number with 0 frequency in the hash array.&nbsp;<\/td><\/tr><tr><td>Using XOR operator<\/td><td class=\"has-text-align-center\" data-align=\"center\">O(N)<\/td><td class=\"has-text-align-center\" data-align=\"center\">O(1)<\/td><td>O(1) as we are not using any extra space<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Conclusion&nbsp;<\/strong><\/h2>\n\n\n\n<p>In conclusion, the Find the Missing Number <a href=\"https:\/\/leetcode.com\/problems\/missing-number\/\" data-type=\"link\" data-id=\"https:\/\/leetcode.com\/problems\/missing-number\/\" target=\"_blank\" rel=\"noreferrer noopener nofollow\">leetcode problem<\/a> can be approached using various methods. We have discussed the approach from brute to hashing to optimal XOR approach.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Understand the leetcode problem to find the missing number and solve it using hashing and the XOR operator approach.<\/p>\n","protected":false},"author":12,"featured_media":1053,"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-1051","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\/1051","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=1051"}],"version-history":[{"count":3,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/1051\/revisions"}],"predecessor-version":[{"id":1083,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/1051\/revisions\/1083"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/media\/1053"}],"wp:attachment":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/media?parent=1051"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/categories?post=1051"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/tags?post=1051"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}