{"id":2479,"date":"2021-10-09T11:17:00","date_gmt":"2021-10-09T05:47:00","guid":{"rendered":"https:\/\/www.interviewbit.com\/blog\/?p=2479"},"modified":"2021-10-08T16:10:52","modified_gmt":"2021-10-08T10:40:52","slug":"find-the-missing-number","status":"publish","type":"post","link":"https:\/\/www.interviewbit.com\/blog\/find-the-missing-number\/","title":{"rendered":"Find The Missing Number"},"content":{"rendered":"\n<div class=\"gutentoc tocactive nostyle\" style=\"max-width:400px\"><div class=\"gutentoc-toc-wrap\"><div class=\"gutentoc-toc-title-wrap\"><div class=\"gutentoc-toc-title\">Table Of Contents<\/div><div id=\"open\" class=\"toggletwo\">show<\/div><\/div><div id=\"toclist\"><div class=\"gutentoc-toc__list-wrap\"><ul class=\"gutentoc-toc__list\"><li><a href=\"#problem-statement\">Problem Statement<\/a><\/li><li><a href=\"#simple-approach\">Simple Approach<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-implementation\">C Implementation<\/a><\/li><li><a href=\"#java-implementation\">Java Implementation<\/a><\/li><li><a href=\"#python-implementation\">Python Implementation<\/a><\/li><\/ul><li><a href=\"#xor-approach\">XoR Approach<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#dry-run-of-xor-approach\">Dry Run of XoR Approach<\/a><\/li><li><a href=\"#c-implementation-of-xor-approach\">C Implementation of XoR Approach<\/a><\/li><li><a href=\"#-java-implementation-of-xor-approach\"><meta charset=\"utf-8\">Java Implementation of XoR Approach<\/a><\/li><li><a href=\"#-python-implementation-of-xor-approach\"><meta charset=\"utf-8\">Python Implementation of XoR Approach<\/a><\/li><\/ul><li><a href=\"#practice-questions\">Practice Questions<\/a><\/li><li><a href=\"#frequently-asked-questions\">Frequently Asked Questions<\/a><\/li><\/ul><\/div><\/div><\/div><\/div>\n\n\n\n<h2 id=\"problem-statement\">Problem Statement<\/h2>\n\n\n\n<p>You are given an array of integers of size N &#8211; 1 ranging from 1 to N. There are no duplicates in the list. One of the integers is missing in the array. The task is to find the missing number in the series.<\/p>\n\n\n\n<p><strong>Examples:<\/strong><\/p>\n\n\n\n<p><strong>Input:<\/strong> list[] = {1, 2, 4, 6, 3, 7, 8,10,5}<br><strong>Output:<\/strong> 9<br><strong>Explanation:<\/strong> The missing number from 1 to 10 is 9.<\/p>\n\n\n\n<p><strong>Input:<\/strong> list[] = {3, 2, 4, 5}<br><strong>Output:<\/strong> 3<br><strong>Explanation:<\/strong> The missing number from 1 to 5 is 1.<\/p>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter size-full\"><img  loading=\"lazy\"  width=\"1024\"  height=\"313\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"Missing Number\"  class=\"wp-image-2485 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 1024px) 100vw, 1024px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Missing-Number.jpg\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Missing-Number.jpg 1024w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Missing-Number-300x92.jpg 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Missing-Number-768x235.jpg 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Missing-Number-380x116.jpg 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Missing-Number-550x168.jpg 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Missing-Number-800x245.jpg 800w\" ><\/figure><\/div>\n\n\n\n<hr class=\"wp-block-separator has-text-color has-background has-black-background-color has-black-color is-style-wide\"\/>\n\n\n\n<h2 id=\"simple-approach\">Simple Approach<\/h2>\n\n\n\n<p>This method uses the formula of summation.<\/p>\n\n\n\n<p>The size of the array is N &#8211; 1. So the sum of n elements, that is the sum of numbers from 1 to N can be calculated by using the formula N * (N + 1) \/ 2. Now find the summation of all elements in the array and subtract it from the summation of first N natural numbers, the value obtained will be the value of the missing element.<\/p>\n\n\n\n<p><strong>Algorithm:<\/strong><\/p>\n\n\n\n<ul><li>Calculate the summation of first N natural numbers as Total = N * (N + 1) \/ 2<\/li><li>Create a variable sum to store the summation of elements of the array.<\/li><li>Iterate the array from start to end.<\/li><li>Updating the value of sum as sum = sum + array[i]<\/li><li>Print the missing number as the Total \u2013 sum<\/li><\/ul>\n\n\n\n<h3 id=\"c-implementation\">C Implementation<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"c\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">int MissingNo(int a[], int n) {\n  int i, total;\n  total = (n + 1) * (n + 2) \/ 2;\n  for (i = 0; i &lt; n; i++)\n    total -= a[i];\n  return total;\n}<\/pre>\n\n\n\n<h3 id=\"java-implementation\">Java Implementation<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">MissingNumbers(int[] arr) {\n  for (int i = 0; i &lt; arr.length; i++) {\n    int index = Math.abs(arr[i]);\n    if (arr[index - 1] > 0) {\n      arr[index - 1] *= -1;\n    }\n  }\n  List &lt; Integer > ans = new ArrayList &lt; > ();\n  for (int i = 0; i &lt; arr.length; i++) {\n    if (arr[i] > 0) {\n      ans.add(i + 1);\n    }\n  }\n  return ans; \n}<\/pre>\n\n\n\n<h3 id=\"python-implementation\">Python Implementation<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">def MissingNo(arr):\n    n = len(arr)\n    total = (n + 1)*(n + 2)\/2\n    arr_sum = sum(arr)\n    return total - arr_sum<\/pre>\n\n\n\n<p><strong>Time Complexity:<\/strong> O(N) where N is the size of the array.<br>Space Complexity: O(1) because no extra space is needed.<\/p>\n\n\n\n<h2 id=\"xor-approach\">XoR Approach<\/h2>\n\n\n\n<p>This method uses the technique of XOR to solve the problem.<\/p>\n\n\n\n<p><strong>Approach:<\/strong> XOR has certain properties Assume<br>a1 ^ a2 ^ a3 ^ \u2026^ an = A1 and a1 ^ a2 ^ a3 ^ \u2026^ an-1 = A2, Then A1 ^ A2 = an<\/p>\n\n\n\n<p><strong>Algorithm:<\/strong><\/p>\n\n\n\n<ul><li>Create two variables a1= 0 and a2 = 0<\/li><li>Iterate from 1 to n with i as the counter.<\/li><li>For every index i update a1 as a1 = a1 ^ i<\/li><li>Now iterate over the array from start to end.<\/li><li>For every index i update a2 as a2 = a2 ^ arr[i]<\/li><li>Print the missing number as a1 ^ a2.<\/li><\/ul>\n\n\n\n<h3 id=\"dry-run-of-xor-approach\">Dry Run of XoR Approach<\/h3>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter size-full\"><img  loading=\"lazy\"  width=\"576\"  height=\"313\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"Dry Run of XoR Approach\"  class=\"wp-image-2484 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 576px) 100vw, 576px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Dry-Run.jpg\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Dry-Run.jpg 576w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Dry-Run-300x163.jpg 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Dry-Run-380x206.jpg 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Dry-Run-550x299.jpg 550w\" ><figcaption>Dry Run of XoR Approach<\/figcaption><\/figure><\/div>\n\n\n\n<h3 id=\"c-implementation-of-xor-approach\">C Implementation of XoR Approach<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"c\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">int MissingNo(int arr[], int n) {\n  int x1 = arr[0];\n  int x2 = 1;\n\n  for (int i = 1; i &lt; n; i++)\n    x1 = x1 ^ arr[i];\n\n  for (int i = 2; i &lt;= n + 1; i++)\n    x2 = x2 ^ i;\n\n  return (x1 ^ x2);\n}<\/pre>\n\n\n\n<h3 id=\"-java-implementation-of-xor-approach\"><span id=\"java-implementation-of-xor-approach\"><meta charset=\"utf-8\">Java Implementation of XoR Approach<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">static int MissingNo(int arr[], int n) {\n  int x1 = arr[0];\n  int x2 = 1;\n\n  for (int i = 1; i &lt; n; i++)\n    x1 = x1 ^ arr[i];\n\n  for (int i = 2; i &lt;= n + 1; i++)\n    x2 = x2 ^ i;\n\n  return (x1 ^ x2);\n}<\/pre>\n\n\n\n<h3 id=\"-python-implementation-of-xor-approach\"><span id=\"python-implementation-of-xor-approach\"><meta charset=\"utf-8\">Python Implementation of XoR Approach<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">def MissingNo(arr, n):\n    x1 = arr[0]\n    x2 = 1\n     \n    for i in range(1, n):\n        x1 = x1 ^ arr[i]\n         \n    for i in range(2, n + 2):\n        x2 = x2 ^ i\n     \n    return x1 ^ x2<\/pre>\n\n\n\n<p><strong>Time Complexity:<\/strong> O(N) where N is the size of the array because only one traversal is needed.<br><strong>Space Complexity:<\/strong> O(1) because no extra space is needed.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-text-color has-background has-black-background-color has-black-color is-style-wide\"\/>\n\n\n\n<h2 id=\"practice-questions\">Practice Questions<\/h2>\n\n\n\n<p><a rel=\"noreferrer noopener\" href=\"https:\/\/www.interviewbit.com\/problems\/first-missing-integer\/\" target=\"_blank\">First Missing Integer<\/a><br><a rel=\"noreferrer noopener\" href=\"https:\/\/www.interviewbit.com\/problems\/repeat-and-missing-number-array\/\" target=\"_blank\">Repeat and Missing Number Array<\/a><\/p>\n\n\n\n<hr class=\"wp-block-separator has-text-color has-background has-black-background-color has-black-color is-style-wide\"\/>\n\n\n\n<h2 id=\"frequently-asked-questions\">Frequently Asked Questions<\/h2>\n\n\n\n<p><strong>What are the constraints of this problem?<\/strong><br>All the numbers in the array should be between 1 to N, where N -1 is the size of the array.<\/p>\n\n\n\n<p><strong>Will these approaches work for larger numbers?<\/strong><br>No, it will only work for numbers less than 10^6 because we can not make an array of greater size.<\/p>\n","protected":false},"excerpt":{"rendered":"Problem Statement You are given an array of integers of size N &#8211; 1 ranging from 1 to&hellip;\n","protected":false},"author":5,"featured_media":2483,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_daextam_enable_autolinks":"","csco_singular_sidebar":"","csco_page_header_type":"","csco_appearance_grid":"","csco_page_load_nextpost":"","csco_post_video_location":[],"csco_post_video_location_hash":"","csco_post_video_url":"","csco_post_video_bg_start_time":0,"csco_post_video_bg_end_time":0},"categories":[145],"tags":[413],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/2479"}],"collection":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/users\/5"}],"replies":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/comments?post=2479"}],"version-history":[{"count":1,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/2479\/revisions"}],"predecessor-version":[{"id":2487,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/2479\/revisions\/2487"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media\/2483"}],"wp:attachment":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media?parent=2479"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/categories?post=2479"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/tags?post=2479"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}