Algorithm - Find the first missing integer in the sequence of integersWhat is the best algorithm for an overridden System.Object.GetHashCode?Easy interview question got harder: given numbers 1..100, find the missing number(s)Find the minimum element missing from sequence of non-negative integersFind an integer not among four billion given onesUkkonen's suffix tree algorithm in plain EnglishImage Processing: Algorithm Improvement for 'Coca-Cola Can' RecognitionFind running median from a stream of integersHow to find time complexity of an algorithmBomb dropping algorithmWhat is the optimal algorithm for the game 2048?

Can I use my Chinese passport to enter China after I acquired another citizenship?

When quoting, must I also copy hyphens used to divide words that continue on the next line?

How must one send away the mother bird?

What linear sensor for a keyboard?

Drawing ramified coverings with tikz

Is there a word to describe the feeling of being transfixed out of horror?

Create all possible words using a set or letters

Engineer refusing to file/disclose patents

Did US corporations pay demonstrators in the German demonstrations against article 13?

My friend sent me a screenshot of a transaction hash, but when I search for it I find divergent data. What happened?

Reply 'no position' while the job posting is still there

How do ground effect vehicles perform turns?

What major Native American tribes were around Santa Fe during the late 1850s?

Open a doc from terminal, but not by its name

Proving a function is onto where f(x)=|x|.

How do I implement a file system driver driver in Linux?

Is it possible to use .desktop files to open local pdf files on specific pages with a browser?

Are lightweight LN wallets vulnerable to transaction withholding?

Could solar power be utilized and substitute coal in the 19th Century

Gibbs free energy in standard state vs. equilibrium

Transformation of random variables and joint distributions

Why is Arduino resetting while driving motors?

How to express sadness?

How much character growth crosses the line into breaking the character



Algorithm - Find the first missing integer in the sequence of integers


What is the best algorithm for an overridden System.Object.GetHashCode?Easy interview question got harder: given numbers 1..100, find the missing number(s)Find the minimum element missing from sequence of non-negative integersFind an integer not among four billion given onesUkkonen's suffix tree algorithm in plain EnglishImage Processing: Algorithm Improvement for 'Coca-Cola Can' RecognitionFind running median from a stream of integersHow to find time complexity of an algorithmBomb dropping algorithmWhat is the optimal algorithm for the game 2048?













1















Find the first missing integer in the sequence of integers



[4,5,1,2,6,7] missing is 3



Then when there is repeated integers



[1,2,2,2,5,8,9] still missing 3



When you also have negative



[-2,0, 1,2,] missing -1



[1,2,3,4,5] missing 6 or 0



Can anyone help me find a good algorithm to cover all these cases. I have an algorithm which covers first 2 cases but not sure how to cover all the cases in effective manner.










share|improve this question



















  • 3





    First of all, sort the sequence. Secondly, remove any duplicates. Thirdly, look for any "gap" between values. Lastly, if no gap is found, the "missing" is the next value after the last element in the (sorted) sequence.

    – Some programmer dude
    Mar 8 at 6:49












  • For the case 1 2 3 4 5 the missing number can also be a 0?

    – Samer Tufail
    Mar 8 at 6:50







  • 2





    Sort and look for diffs > 1, if you find a difference of 0 it's a duplicate and just continue.

    – Samer Tufail
    Mar 8 at 6:54






  • 3





    Before you can talk about things that are missing you have to talk about the rules for what you expect to be present. You say in a comment that the sequence 1 2 3 4 5 can be missing 0, then why isn't 0 the first missing integer from the first and second sequence in your question as well? Additionally, in the question you say 6 is the number that is missing. Well, is it 0 or 6? How do you define "first"? Please define the rules for which integers you expect to be present.

    – Lasse Vågsæther Karlsen
    Mar 8 at 7:44







  • 1





    The second example is also missing 4, 6, 7. Also, isn't every sequence 'missing' the numbers just off the ends of the sequence?

    – Dave
    Mar 8 at 12:05















1















Find the first missing integer in the sequence of integers



[4,5,1,2,6,7] missing is 3



Then when there is repeated integers



[1,2,2,2,5,8,9] still missing 3



When you also have negative



[-2,0, 1,2,] missing -1



[1,2,3,4,5] missing 6 or 0



Can anyone help me find a good algorithm to cover all these cases. I have an algorithm which covers first 2 cases but not sure how to cover all the cases in effective manner.










share|improve this question



















  • 3





    First of all, sort the sequence. Secondly, remove any duplicates. Thirdly, look for any "gap" between values. Lastly, if no gap is found, the "missing" is the next value after the last element in the (sorted) sequence.

    – Some programmer dude
    Mar 8 at 6:49












  • For the case 1 2 3 4 5 the missing number can also be a 0?

    – Samer Tufail
    Mar 8 at 6:50







  • 2





    Sort and look for diffs > 1, if you find a difference of 0 it's a duplicate and just continue.

    – Samer Tufail
    Mar 8 at 6:54






  • 3





    Before you can talk about things that are missing you have to talk about the rules for what you expect to be present. You say in a comment that the sequence 1 2 3 4 5 can be missing 0, then why isn't 0 the first missing integer from the first and second sequence in your question as well? Additionally, in the question you say 6 is the number that is missing. Well, is it 0 or 6? How do you define "first"? Please define the rules for which integers you expect to be present.

    – Lasse Vågsæther Karlsen
    Mar 8 at 7:44







  • 1





    The second example is also missing 4, 6, 7. Also, isn't every sequence 'missing' the numbers just off the ends of the sequence?

    – Dave
    Mar 8 at 12:05













1












1








1








Find the first missing integer in the sequence of integers



[4,5,1,2,6,7] missing is 3



Then when there is repeated integers



[1,2,2,2,5,8,9] still missing 3



When you also have negative



[-2,0, 1,2,] missing -1



[1,2,3,4,5] missing 6 or 0



Can anyone help me find a good algorithm to cover all these cases. I have an algorithm which covers first 2 cases but not sure how to cover all the cases in effective manner.










share|improve this question
















Find the first missing integer in the sequence of integers



[4,5,1,2,6,7] missing is 3



Then when there is repeated integers



[1,2,2,2,5,8,9] still missing 3



When you also have negative



[-2,0, 1,2,] missing -1



[1,2,3,4,5] missing 6 or 0



Can anyone help me find a good algorithm to cover all these cases. I have an algorithm which covers first 2 cases but not sure how to cover all the cases in effective manner.







algorithm






share|improve this question















share|improve this question













share|improve this question




share|improve this question








edited Mar 8 at 7:46







Hussain ali

















asked Mar 8 at 6:44









Hussain aliHussain ali

104213




104213







  • 3





    First of all, sort the sequence. Secondly, remove any duplicates. Thirdly, look for any "gap" between values. Lastly, if no gap is found, the "missing" is the next value after the last element in the (sorted) sequence.

    – Some programmer dude
    Mar 8 at 6:49












  • For the case 1 2 3 4 5 the missing number can also be a 0?

    – Samer Tufail
    Mar 8 at 6:50







  • 2





    Sort and look for diffs > 1, if you find a difference of 0 it's a duplicate and just continue.

    – Samer Tufail
    Mar 8 at 6:54






  • 3





    Before you can talk about things that are missing you have to talk about the rules for what you expect to be present. You say in a comment that the sequence 1 2 3 4 5 can be missing 0, then why isn't 0 the first missing integer from the first and second sequence in your question as well? Additionally, in the question you say 6 is the number that is missing. Well, is it 0 or 6? How do you define "first"? Please define the rules for which integers you expect to be present.

    – Lasse Vågsæther Karlsen
    Mar 8 at 7:44







  • 1





    The second example is also missing 4, 6, 7. Also, isn't every sequence 'missing' the numbers just off the ends of the sequence?

    – Dave
    Mar 8 at 12:05












  • 3





    First of all, sort the sequence. Secondly, remove any duplicates. Thirdly, look for any "gap" between values. Lastly, if no gap is found, the "missing" is the next value after the last element in the (sorted) sequence.

    – Some programmer dude
    Mar 8 at 6:49












  • For the case 1 2 3 4 5 the missing number can also be a 0?

    – Samer Tufail
    Mar 8 at 6:50







  • 2





    Sort and look for diffs > 1, if you find a difference of 0 it's a duplicate and just continue.

    – Samer Tufail
    Mar 8 at 6:54






  • 3





    Before you can talk about things that are missing you have to talk about the rules for what you expect to be present. You say in a comment that the sequence 1 2 3 4 5 can be missing 0, then why isn't 0 the first missing integer from the first and second sequence in your question as well? Additionally, in the question you say 6 is the number that is missing. Well, is it 0 or 6? How do you define "first"? Please define the rules for which integers you expect to be present.

    – Lasse Vågsæther Karlsen
    Mar 8 at 7:44







  • 1





    The second example is also missing 4, 6, 7. Also, isn't every sequence 'missing' the numbers just off the ends of the sequence?

    – Dave
    Mar 8 at 12:05







3




3





First of all, sort the sequence. Secondly, remove any duplicates. Thirdly, look for any "gap" between values. Lastly, if no gap is found, the "missing" is the next value after the last element in the (sorted) sequence.

– Some programmer dude
Mar 8 at 6:49






First of all, sort the sequence. Secondly, remove any duplicates. Thirdly, look for any "gap" between values. Lastly, if no gap is found, the "missing" is the next value after the last element in the (sorted) sequence.

– Some programmer dude
Mar 8 at 6:49














For the case 1 2 3 4 5 the missing number can also be a 0?

– Samer Tufail
Mar 8 at 6:50






For the case 1 2 3 4 5 the missing number can also be a 0?

– Samer Tufail
Mar 8 at 6:50





2




2





Sort and look for diffs > 1, if you find a difference of 0 it's a duplicate and just continue.

– Samer Tufail
Mar 8 at 6:54





Sort and look for diffs > 1, if you find a difference of 0 it's a duplicate and just continue.

– Samer Tufail
Mar 8 at 6:54




3




3





Before you can talk about things that are missing you have to talk about the rules for what you expect to be present. You say in a comment that the sequence 1 2 3 4 5 can be missing 0, then why isn't 0 the first missing integer from the first and second sequence in your question as well? Additionally, in the question you say 6 is the number that is missing. Well, is it 0 or 6? How do you define "first"? Please define the rules for which integers you expect to be present.

– Lasse Vågsæther Karlsen
Mar 8 at 7:44






Before you can talk about things that are missing you have to talk about the rules for what you expect to be present. You say in a comment that the sequence 1 2 3 4 5 can be missing 0, then why isn't 0 the first missing integer from the first and second sequence in your question as well? Additionally, in the question you say 6 is the number that is missing. Well, is it 0 or 6? How do you define "first"? Please define the rules for which integers you expect to be present.

– Lasse Vågsæther Karlsen
Mar 8 at 7:44





1




1





The second example is also missing 4, 6, 7. Also, isn't every sequence 'missing' the numbers just off the ends of the sequence?

– Dave
Mar 8 at 12:05





The second example is also missing 4, 6, 7. Also, isn't every sequence 'missing' the numbers just off the ends of the sequence?

– Dave
Mar 8 at 12:05












4 Answers
4






active

oldest

votes


















2














What I consider the classic O(n) solution for this problem is to rely on the fact that the array can contain at most N unique numbers, where N is the input's length. Therefore the range for our record is restricted to N.



Since you seem to allow the expected sequence to start anywhere, including negative numbers, we can start by iterating once over the array and recording, L, the lowest number seen. Now use L as an offset so that 0 + L equals the first number we expect to be present.



Initialise an array record of length (N + 1) and set each entry to false. Iterate over the input and for each entry, A[i], if (A[i] - L) is not greater than N, set record[ A[i] - L ] to true. For example:



[-2, 0, 1, 2] ->
N = 4
L = -2

-2 -> -2 - (-2) = 0
-> record[0] = true

0 -> 0 - (-2) = 2
-> record[2] = true

1 -> 1 - (-2) = 3
-> record[3] = true

2 -> 2 - (-2) = 4
-> record[4] = true

record -> [true, false, true, true, true]


Now iterate over the record. Output the first entry at index i that is set to false as i + L. In our example above, this would be:



record[1] is false

output: 1 + (-2) -> -1





share|improve this answer






























    1














    I think, it will be easy to solve sort of problems using data-structure like TreeMap in JAVA, e.g:



    treeMap.put(array[i], treeMap.get(array[i]) == null ? 1 : treeMap.get(array[i]) + 1);


    So, you are putting key and value to the TreeMap the key represent the digit itself e.g, 1,2,3... and the value represent the occurrence times.



    Thus, and by taking advantage of this data-structure (Sort elements for us) you can loop through this data-structure and check which key is missing in the sequence, e.g:



    for key in treeMap
    if(key > currentIndex) // this is the missing digit
    if(loop-completed-without-missing-key) // it's not in the array.





    share|improve this answer






























      1














      Add the numbers to a running array and keep them sorted.



      You may also have optional minimum and maximum bounds for the array (to handle your third case, "6 is missing even if not in array"



      On examination of a new number:
      - try inserting it in the sorting array.
      - already present: discard
      - below minimum or above maximum: nullify minimum or maximum accordingly
      - otherwise add in proper position.



      To handle an array: sort it, compare first and last elements to expected minimum / maximum. Nullify minimum if greater than first element, nullify maximum if smaller than last element.



      There might be a special case if minimum and maximum are both above first or both above last:



       min=5 max=8 array = [ 10, 11, 13 ]

      Here 5, 6, 7, 8 and 12 are missing, but what about 9? Should it be considered missing?


      When checking for missing numbers include:
      - if minimum is not null, all numbers from minimum to first element.
      - if maximum is not null, all numbers from last element to maximum.
      - if (last - first) = number of elements, no numbers are missing
      (total numbers examined minus array size is duplicate count)
      - otherwise walk the array and report all missing numbers: when
      checking array[i], if array[i]-array[i-1] != 1 you have a gap.



      only "first" missing



      You still have to manage the whole array even if you're only interested in one missing number. For if you discarded part of the array, and the missing number arrived, then the new missing number might well have been in the discarded part of the array.



      However you might keep trace of what the smallest missing number is, and recalculate with cost of o(log n) only when/if it arrives; then you'd be able to tell which is it in o(1) time. To quickly zero on that missing number, consider that there is a gap between arr[i] and arr[j] iff arr[j]-arr[i] > j-i.



      So you can use the bisection method: start with i = first, j = last; if gap(i,j) then c = ceil(i+j)/2. If gap(i, c) then j = c, else i = c, and repeat until j-i = 1. At that point arr[i]+1 is your smallest missing number.






      share|improve this answer
































        1














        #include <stdio.h>
        #include <string.h>
        #include <math.h>
        #include <stdlib.h>

        int main()

        int n;
        scanf("%d",&n);
        int a[n],i=0;
        //Reading elements
        for(i=0;i<n;i++)
        scanf("%d",&a[i]);

        int min=__INT_MAX__,max=0;
        //Finding the minimun and maximum from given elements
        for(i=0;i<n;i++)
        if(a[i]>max)
        max=a[i];
        if(a[i]<min)
        min=a[i];

        int len=max-min,diff=0-min,miss;
        int b[len];
        //Creating a new array and assigning 0
        for(i=0;i<len;i++)
        b[i]=0;
        //The corresponding index value is incremented based on the given numbers
        for(i=0;i<n;i++)
        b[a[i]+diff]++;

        //Finding the missed value
        for(i=0;i<len;i++)
        if(b[i]==0)
        miss=i-diff;
        break;


        printf("%d",miss);



        Code Explanation:




        1.Find the minimum and maximum in the given numbers.



        2.Create an count array of size (maximum-minimum) and iniatizing to 0, which maintains the count of the given numbers.



        3.Now by iterating, for each given element increment the corresponding index by 1.



        4.Finally iterate through the count array and find the first missing number.



        This might help you in solving your problem. Correct me if i'm wrong.






        share|improve this answer






















          Your Answer






          StackExchange.ifUsing("editor", function ()
          StackExchange.using("externalEditor", function ()
          StackExchange.using("snippets", function ()
          StackExchange.snippets.init();
          );
          );
          , "code-snippets");

          StackExchange.ready(function()
          var channelOptions =
          tags: "".split(" "),
          id: "1"
          ;
          initTagRenderer("".split(" "), "".split(" "), channelOptions);

          StackExchange.using("externalEditor", function()
          // Have to fire editor after snippets, if snippets enabled
          if (StackExchange.settings.snippets.snippetsEnabled)
          StackExchange.using("snippets", function()
          createEditor();
          );

          else
          createEditor();

          );

          function createEditor()
          StackExchange.prepareEditor(
          heartbeatType: 'answer',
          autoActivateHeartbeat: false,
          convertImagesToLinks: true,
          noModals: true,
          showLowRepImageUploadWarning: true,
          reputationToPostImages: 10,
          bindNavPrevention: true,
          postfix: "",
          imageUploader:
          brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
          contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
          allowUrls: true
          ,
          onDemand: true,
          discardSelector: ".discard-answer"
          ,immediatelyShowMarkdownHelp:true
          );



          );













          draft saved

          draft discarded


















          StackExchange.ready(
          function ()
          StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f55058040%2falgorithm-find-the-first-missing-integer-in-the-sequence-of-integers%23new-answer', 'question_page');

          );

          Post as a guest















          Required, but never shown

























          4 Answers
          4






          active

          oldest

          votes








          4 Answers
          4






          active

          oldest

          votes









          active

          oldest

          votes






          active

          oldest

          votes









          2














          What I consider the classic O(n) solution for this problem is to rely on the fact that the array can contain at most N unique numbers, where N is the input's length. Therefore the range for our record is restricted to N.



          Since you seem to allow the expected sequence to start anywhere, including negative numbers, we can start by iterating once over the array and recording, L, the lowest number seen. Now use L as an offset so that 0 + L equals the first number we expect to be present.



          Initialise an array record of length (N + 1) and set each entry to false. Iterate over the input and for each entry, A[i], if (A[i] - L) is not greater than N, set record[ A[i] - L ] to true. For example:



          [-2, 0, 1, 2] ->
          N = 4
          L = -2

          -2 -> -2 - (-2) = 0
          -> record[0] = true

          0 -> 0 - (-2) = 2
          -> record[2] = true

          1 -> 1 - (-2) = 3
          -> record[3] = true

          2 -> 2 - (-2) = 4
          -> record[4] = true

          record -> [true, false, true, true, true]


          Now iterate over the record. Output the first entry at index i that is set to false as i + L. In our example above, this would be:



          record[1] is false

          output: 1 + (-2) -> -1





          share|improve this answer



























            2














            What I consider the classic O(n) solution for this problem is to rely on the fact that the array can contain at most N unique numbers, where N is the input's length. Therefore the range for our record is restricted to N.



            Since you seem to allow the expected sequence to start anywhere, including negative numbers, we can start by iterating once over the array and recording, L, the lowest number seen. Now use L as an offset so that 0 + L equals the first number we expect to be present.



            Initialise an array record of length (N + 1) and set each entry to false. Iterate over the input and for each entry, A[i], if (A[i] - L) is not greater than N, set record[ A[i] - L ] to true. For example:



            [-2, 0, 1, 2] ->
            N = 4
            L = -2

            -2 -> -2 - (-2) = 0
            -> record[0] = true

            0 -> 0 - (-2) = 2
            -> record[2] = true

            1 -> 1 - (-2) = 3
            -> record[3] = true

            2 -> 2 - (-2) = 4
            -> record[4] = true

            record -> [true, false, true, true, true]


            Now iterate over the record. Output the first entry at index i that is set to false as i + L. In our example above, this would be:



            record[1] is false

            output: 1 + (-2) -> -1





            share|improve this answer

























              2












              2








              2







              What I consider the classic O(n) solution for this problem is to rely on the fact that the array can contain at most N unique numbers, where N is the input's length. Therefore the range for our record is restricted to N.



              Since you seem to allow the expected sequence to start anywhere, including negative numbers, we can start by iterating once over the array and recording, L, the lowest number seen. Now use L as an offset so that 0 + L equals the first number we expect to be present.



              Initialise an array record of length (N + 1) and set each entry to false. Iterate over the input and for each entry, A[i], if (A[i] - L) is not greater than N, set record[ A[i] - L ] to true. For example:



              [-2, 0, 1, 2] ->
              N = 4
              L = -2

              -2 -> -2 - (-2) = 0
              -> record[0] = true

              0 -> 0 - (-2) = 2
              -> record[2] = true

              1 -> 1 - (-2) = 3
              -> record[3] = true

              2 -> 2 - (-2) = 4
              -> record[4] = true

              record -> [true, false, true, true, true]


              Now iterate over the record. Output the first entry at index i that is set to false as i + L. In our example above, this would be:



              record[1] is false

              output: 1 + (-2) -> -1





              share|improve this answer













              What I consider the classic O(n) solution for this problem is to rely on the fact that the array can contain at most N unique numbers, where N is the input's length. Therefore the range for our record is restricted to N.



              Since you seem to allow the expected sequence to start anywhere, including negative numbers, we can start by iterating once over the array and recording, L, the lowest number seen. Now use L as an offset so that 0 + L equals the first number we expect to be present.



              Initialise an array record of length (N + 1) and set each entry to false. Iterate over the input and for each entry, A[i], if (A[i] - L) is not greater than N, set record[ A[i] - L ] to true. For example:



              [-2, 0, 1, 2] ->
              N = 4
              L = -2

              -2 -> -2 - (-2) = 0
              -> record[0] = true

              0 -> 0 - (-2) = 2
              -> record[2] = true

              1 -> 1 - (-2) = 3
              -> record[3] = true

              2 -> 2 - (-2) = 4
              -> record[4] = true

              record -> [true, false, true, true, true]


              Now iterate over the record. Output the first entry at index i that is set to false as i + L. In our example above, this would be:



              record[1] is false

              output: 1 + (-2) -> -1






              share|improve this answer












              share|improve this answer



              share|improve this answer










              answered Mar 8 at 11:47









              גלעד ברקןגלעד ברקן

              13.4k21544




              13.4k21544























                  1














                  I think, it will be easy to solve sort of problems using data-structure like TreeMap in JAVA, e.g:



                  treeMap.put(array[i], treeMap.get(array[i]) == null ? 1 : treeMap.get(array[i]) + 1);


                  So, you are putting key and value to the TreeMap the key represent the digit itself e.g, 1,2,3... and the value represent the occurrence times.



                  Thus, and by taking advantage of this data-structure (Sort elements for us) you can loop through this data-structure and check which key is missing in the sequence, e.g:



                  for key in treeMap
                  if(key > currentIndex) // this is the missing digit
                  if(loop-completed-without-missing-key) // it's not in the array.





                  share|improve this answer



























                    1














                    I think, it will be easy to solve sort of problems using data-structure like TreeMap in JAVA, e.g:



                    treeMap.put(array[i], treeMap.get(array[i]) == null ? 1 : treeMap.get(array[i]) + 1);


                    So, you are putting key and value to the TreeMap the key represent the digit itself e.g, 1,2,3... and the value represent the occurrence times.



                    Thus, and by taking advantage of this data-structure (Sort elements for us) you can loop through this data-structure and check which key is missing in the sequence, e.g:



                    for key in treeMap
                    if(key > currentIndex) // this is the missing digit
                    if(loop-completed-without-missing-key) // it's not in the array.





                    share|improve this answer

























                      1












                      1








                      1







                      I think, it will be easy to solve sort of problems using data-structure like TreeMap in JAVA, e.g:



                      treeMap.put(array[i], treeMap.get(array[i]) == null ? 1 : treeMap.get(array[i]) + 1);


                      So, you are putting key and value to the TreeMap the key represent the digit itself e.g, 1,2,3... and the value represent the occurrence times.



                      Thus, and by taking advantage of this data-structure (Sort elements for us) you can loop through this data-structure and check which key is missing in the sequence, e.g:



                      for key in treeMap
                      if(key > currentIndex) // this is the missing digit
                      if(loop-completed-without-missing-key) // it's not in the array.





                      share|improve this answer













                      I think, it will be easy to solve sort of problems using data-structure like TreeMap in JAVA, e.g:



                      treeMap.put(array[i], treeMap.get(array[i]) == null ? 1 : treeMap.get(array[i]) + 1);


                      So, you are putting key and value to the TreeMap the key represent the digit itself e.g, 1,2,3... and the value represent the occurrence times.



                      Thus, and by taking advantage of this data-structure (Sort elements for us) you can loop through this data-structure and check which key is missing in the sequence, e.g:



                      for key in treeMap
                      if(key > currentIndex) // this is the missing digit
                      if(loop-completed-without-missing-key) // it's not in the array.






                      share|improve this answer












                      share|improve this answer



                      share|improve this answer










                      answered Mar 8 at 7:29









                      Ibrahim AliIbrahim Ali

                      769




                      769





















                          1














                          Add the numbers to a running array and keep them sorted.



                          You may also have optional minimum and maximum bounds for the array (to handle your third case, "6 is missing even if not in array"



                          On examination of a new number:
                          - try inserting it in the sorting array.
                          - already present: discard
                          - below minimum or above maximum: nullify minimum or maximum accordingly
                          - otherwise add in proper position.



                          To handle an array: sort it, compare first and last elements to expected minimum / maximum. Nullify minimum if greater than first element, nullify maximum if smaller than last element.



                          There might be a special case if minimum and maximum are both above first or both above last:



                           min=5 max=8 array = [ 10, 11, 13 ]

                          Here 5, 6, 7, 8 and 12 are missing, but what about 9? Should it be considered missing?


                          When checking for missing numbers include:
                          - if minimum is not null, all numbers from minimum to first element.
                          - if maximum is not null, all numbers from last element to maximum.
                          - if (last - first) = number of elements, no numbers are missing
                          (total numbers examined minus array size is duplicate count)
                          - otherwise walk the array and report all missing numbers: when
                          checking array[i], if array[i]-array[i-1] != 1 you have a gap.



                          only "first" missing



                          You still have to manage the whole array even if you're only interested in one missing number. For if you discarded part of the array, and the missing number arrived, then the new missing number might well have been in the discarded part of the array.



                          However you might keep trace of what the smallest missing number is, and recalculate with cost of o(log n) only when/if it arrives; then you'd be able to tell which is it in o(1) time. To quickly zero on that missing number, consider that there is a gap between arr[i] and arr[j] iff arr[j]-arr[i] > j-i.



                          So you can use the bisection method: start with i = first, j = last; if gap(i,j) then c = ceil(i+j)/2. If gap(i, c) then j = c, else i = c, and repeat until j-i = 1. At that point arr[i]+1 is your smallest missing number.






                          share|improve this answer





























                            1














                            Add the numbers to a running array and keep them sorted.



                            You may also have optional minimum and maximum bounds for the array (to handle your third case, "6 is missing even if not in array"



                            On examination of a new number:
                            - try inserting it in the sorting array.
                            - already present: discard
                            - below minimum or above maximum: nullify minimum or maximum accordingly
                            - otherwise add in proper position.



                            To handle an array: sort it, compare first and last elements to expected minimum / maximum. Nullify minimum if greater than first element, nullify maximum if smaller than last element.



                            There might be a special case if minimum and maximum are both above first or both above last:



                             min=5 max=8 array = [ 10, 11, 13 ]

                            Here 5, 6, 7, 8 and 12 are missing, but what about 9? Should it be considered missing?


                            When checking for missing numbers include:
                            - if minimum is not null, all numbers from minimum to first element.
                            - if maximum is not null, all numbers from last element to maximum.
                            - if (last - first) = number of elements, no numbers are missing
                            (total numbers examined minus array size is duplicate count)
                            - otherwise walk the array and report all missing numbers: when
                            checking array[i], if array[i]-array[i-1] != 1 you have a gap.



                            only "first" missing



                            You still have to manage the whole array even if you're only interested in one missing number. For if you discarded part of the array, and the missing number arrived, then the new missing number might well have been in the discarded part of the array.



                            However you might keep trace of what the smallest missing number is, and recalculate with cost of o(log n) only when/if it arrives; then you'd be able to tell which is it in o(1) time. To quickly zero on that missing number, consider that there is a gap between arr[i] and arr[j] iff arr[j]-arr[i] > j-i.



                            So you can use the bisection method: start with i = first, j = last; if gap(i,j) then c = ceil(i+j)/2. If gap(i, c) then j = c, else i = c, and repeat until j-i = 1. At that point arr[i]+1 is your smallest missing number.






                            share|improve this answer



























                              1












                              1








                              1







                              Add the numbers to a running array and keep them sorted.



                              You may also have optional minimum and maximum bounds for the array (to handle your third case, "6 is missing even if not in array"



                              On examination of a new number:
                              - try inserting it in the sorting array.
                              - already present: discard
                              - below minimum or above maximum: nullify minimum or maximum accordingly
                              - otherwise add in proper position.



                              To handle an array: sort it, compare first and last elements to expected minimum / maximum. Nullify minimum if greater than first element, nullify maximum if smaller than last element.



                              There might be a special case if minimum and maximum are both above first or both above last:



                               min=5 max=8 array = [ 10, 11, 13 ]

                              Here 5, 6, 7, 8 and 12 are missing, but what about 9? Should it be considered missing?


                              When checking for missing numbers include:
                              - if minimum is not null, all numbers from minimum to first element.
                              - if maximum is not null, all numbers from last element to maximum.
                              - if (last - first) = number of elements, no numbers are missing
                              (total numbers examined minus array size is duplicate count)
                              - otherwise walk the array and report all missing numbers: when
                              checking array[i], if array[i]-array[i-1] != 1 you have a gap.



                              only "first" missing



                              You still have to manage the whole array even if you're only interested in one missing number. For if you discarded part of the array, and the missing number arrived, then the new missing number might well have been in the discarded part of the array.



                              However you might keep trace of what the smallest missing number is, and recalculate with cost of o(log n) only when/if it arrives; then you'd be able to tell which is it in o(1) time. To quickly zero on that missing number, consider that there is a gap between arr[i] and arr[j] iff arr[j]-arr[i] > j-i.



                              So you can use the bisection method: start with i = first, j = last; if gap(i,j) then c = ceil(i+j)/2. If gap(i, c) then j = c, else i = c, and repeat until j-i = 1. At that point arr[i]+1 is your smallest missing number.






                              share|improve this answer















                              Add the numbers to a running array and keep them sorted.



                              You may also have optional minimum and maximum bounds for the array (to handle your third case, "6 is missing even if not in array"



                              On examination of a new number:
                              - try inserting it in the sorting array.
                              - already present: discard
                              - below minimum or above maximum: nullify minimum or maximum accordingly
                              - otherwise add in proper position.



                              To handle an array: sort it, compare first and last elements to expected minimum / maximum. Nullify minimum if greater than first element, nullify maximum if smaller than last element.



                              There might be a special case if minimum and maximum are both above first or both above last:



                               min=5 max=8 array = [ 10, 11, 13 ]

                              Here 5, 6, 7, 8 and 12 are missing, but what about 9? Should it be considered missing?


                              When checking for missing numbers include:
                              - if minimum is not null, all numbers from minimum to first element.
                              - if maximum is not null, all numbers from last element to maximum.
                              - if (last - first) = number of elements, no numbers are missing
                              (total numbers examined minus array size is duplicate count)
                              - otherwise walk the array and report all missing numbers: when
                              checking array[i], if array[i]-array[i-1] != 1 you have a gap.



                              only "first" missing



                              You still have to manage the whole array even if you're only interested in one missing number. For if you discarded part of the array, and the missing number arrived, then the new missing number might well have been in the discarded part of the array.



                              However you might keep trace of what the smallest missing number is, and recalculate with cost of o(log n) only when/if it arrives; then you'd be able to tell which is it in o(1) time. To quickly zero on that missing number, consider that there is a gap between arr[i] and arr[j] iff arr[j]-arr[i] > j-i.



                              So you can use the bisection method: start with i = first, j = last; if gap(i,j) then c = ceil(i+j)/2. If gap(i, c) then j = c, else i = c, and repeat until j-i = 1. At that point arr[i]+1 is your smallest missing number.







                              share|improve this answer














                              share|improve this answer



                              share|improve this answer








                              edited Mar 8 at 7:46

























                              answered Mar 8 at 7:40









                              LSerniLSerni

                              41.4k64882




                              41.4k64882





















                                  1














                                  #include <stdio.h>
                                  #include <string.h>
                                  #include <math.h>
                                  #include <stdlib.h>

                                  int main()

                                  int n;
                                  scanf("%d",&n);
                                  int a[n],i=0;
                                  //Reading elements
                                  for(i=0;i<n;i++)
                                  scanf("%d",&a[i]);

                                  int min=__INT_MAX__,max=0;
                                  //Finding the minimun and maximum from given elements
                                  for(i=0;i<n;i++)
                                  if(a[i]>max)
                                  max=a[i];
                                  if(a[i]<min)
                                  min=a[i];

                                  int len=max-min,diff=0-min,miss;
                                  int b[len];
                                  //Creating a new array and assigning 0
                                  for(i=0;i<len;i++)
                                  b[i]=0;
                                  //The corresponding index value is incremented based on the given numbers
                                  for(i=0;i<n;i++)
                                  b[a[i]+diff]++;

                                  //Finding the missed value
                                  for(i=0;i<len;i++)
                                  if(b[i]==0)
                                  miss=i-diff;
                                  break;


                                  printf("%d",miss);



                                  Code Explanation:




                                  1.Find the minimum and maximum in the given numbers.



                                  2.Create an count array of size (maximum-minimum) and iniatizing to 0, which maintains the count of the given numbers.



                                  3.Now by iterating, for each given element increment the corresponding index by 1.



                                  4.Finally iterate through the count array and find the first missing number.



                                  This might help you in solving your problem. Correct me if i'm wrong.






                                  share|improve this answer



























                                    1














                                    #include <stdio.h>
                                    #include <string.h>
                                    #include <math.h>
                                    #include <stdlib.h>

                                    int main()

                                    int n;
                                    scanf("%d",&n);
                                    int a[n],i=0;
                                    //Reading elements
                                    for(i=0;i<n;i++)
                                    scanf("%d",&a[i]);

                                    int min=__INT_MAX__,max=0;
                                    //Finding the minimun and maximum from given elements
                                    for(i=0;i<n;i++)
                                    if(a[i]>max)
                                    max=a[i];
                                    if(a[i]<min)
                                    min=a[i];

                                    int len=max-min,diff=0-min,miss;
                                    int b[len];
                                    //Creating a new array and assigning 0
                                    for(i=0;i<len;i++)
                                    b[i]=0;
                                    //The corresponding index value is incremented based on the given numbers
                                    for(i=0;i<n;i++)
                                    b[a[i]+diff]++;

                                    //Finding the missed value
                                    for(i=0;i<len;i++)
                                    if(b[i]==0)
                                    miss=i-diff;
                                    break;


                                    printf("%d",miss);



                                    Code Explanation:




                                    1.Find the minimum and maximum in the given numbers.



                                    2.Create an count array of size (maximum-minimum) and iniatizing to 0, which maintains the count of the given numbers.



                                    3.Now by iterating, for each given element increment the corresponding index by 1.



                                    4.Finally iterate through the count array and find the first missing number.



                                    This might help you in solving your problem. Correct me if i'm wrong.






                                    share|improve this answer

























                                      1












                                      1








                                      1







                                      #include <stdio.h>
                                      #include <string.h>
                                      #include <math.h>
                                      #include <stdlib.h>

                                      int main()

                                      int n;
                                      scanf("%d",&n);
                                      int a[n],i=0;
                                      //Reading elements
                                      for(i=0;i<n;i++)
                                      scanf("%d",&a[i]);

                                      int min=__INT_MAX__,max=0;
                                      //Finding the minimun and maximum from given elements
                                      for(i=0;i<n;i++)
                                      if(a[i]>max)
                                      max=a[i];
                                      if(a[i]<min)
                                      min=a[i];

                                      int len=max-min,diff=0-min,miss;
                                      int b[len];
                                      //Creating a new array and assigning 0
                                      for(i=0;i<len;i++)
                                      b[i]=0;
                                      //The corresponding index value is incremented based on the given numbers
                                      for(i=0;i<n;i++)
                                      b[a[i]+diff]++;

                                      //Finding the missed value
                                      for(i=0;i<len;i++)
                                      if(b[i]==0)
                                      miss=i-diff;
                                      break;


                                      printf("%d",miss);



                                      Code Explanation:




                                      1.Find the minimum and maximum in the given numbers.



                                      2.Create an count array of size (maximum-minimum) and iniatizing to 0, which maintains the count of the given numbers.



                                      3.Now by iterating, for each given element increment the corresponding index by 1.



                                      4.Finally iterate through the count array and find the first missing number.



                                      This might help you in solving your problem. Correct me if i'm wrong.






                                      share|improve this answer













                                      #include <stdio.h>
                                      #include <string.h>
                                      #include <math.h>
                                      #include <stdlib.h>

                                      int main()

                                      int n;
                                      scanf("%d",&n);
                                      int a[n],i=0;
                                      //Reading elements
                                      for(i=0;i<n;i++)
                                      scanf("%d",&a[i]);

                                      int min=__INT_MAX__,max=0;
                                      //Finding the minimun and maximum from given elements
                                      for(i=0;i<n;i++)
                                      if(a[i]>max)
                                      max=a[i];
                                      if(a[i]<min)
                                      min=a[i];

                                      int len=max-min,diff=0-min,miss;
                                      int b[len];
                                      //Creating a new array and assigning 0
                                      for(i=0;i<len;i++)
                                      b[i]=0;
                                      //The corresponding index value is incremented based on the given numbers
                                      for(i=0;i<n;i++)
                                      b[a[i]+diff]++;

                                      //Finding the missed value
                                      for(i=0;i<len;i++)
                                      if(b[i]==0)
                                      miss=i-diff;
                                      break;


                                      printf("%d",miss);



                                      Code Explanation:




                                      1.Find the minimum and maximum in the given numbers.



                                      2.Create an count array of size (maximum-minimum) and iniatizing to 0, which maintains the count of the given numbers.



                                      3.Now by iterating, for each given element increment the corresponding index by 1.



                                      4.Finally iterate through the count array and find the first missing number.



                                      This might help you in solving your problem. Correct me if i'm wrong.







                                      share|improve this answer












                                      share|improve this answer



                                      share|improve this answer










                                      answered Mar 8 at 12:39









                                      Suhas_mudamSuhas_mudam

                                      236




                                      236



























                                          draft saved

                                          draft discarded
















































                                          Thanks for contributing an answer to Stack Overflow!


                                          • Please be sure to answer the question. Provide details and share your research!

                                          But avoid


                                          • Asking for help, clarification, or responding to other answers.

                                          • Making statements based on opinion; back them up with references or personal experience.

                                          To learn more, see our tips on writing great answers.




                                          draft saved


                                          draft discarded














                                          StackExchange.ready(
                                          function ()
                                          StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f55058040%2falgorithm-find-the-first-missing-integer-in-the-sequence-of-integers%23new-answer', 'question_page');

                                          );

                                          Post as a guest















                                          Required, but never shown





















































                                          Required, but never shown














                                          Required, but never shown












                                          Required, but never shown







                                          Required, but never shown

































                                          Required, but never shown














                                          Required, but never shown












                                          Required, but never shown







                                          Required, but never shown







                                          Popular posts from this blog

                                          Identity Server 4 is not redirecting to Angular app after login2019 Community Moderator ElectionIdentity Server 4 and dockerIdentityserver implicit flow unauthorized_clientIdentityServer Hybrid Flow - Access Token is null after user successful loginIdentity Server to MVC client : Page Redirect After loginLogin with Steam OpenId(oidc-client-js)Identity Server 4+.NET Core 2.0 + IdentityIdentityServer4 post-login redirect not working in Edge browserCall to IdentityServer4 generates System.NullReferenceException: Object reference not set to an instance of an objectIdentityServer4 without HTTPS not workingHow to get Authorization code from identity server without login form

                                          2005 Ahvaz unrest Contents Background Causes Casualties Aftermath See also References Navigation menue"At Least 10 Are Killed by Bombs in Iran""Iran"Archived"Arab-Iranians in Iran to make April 15 'Day of Fury'"State of Mind, State of Order: Reactions to Ethnic Unrest in the Islamic Republic of Iran.10.1111/j.1754-9469.2008.00028.x"Iran hangs Arab separatists"Iran Overview from ArchivedConstitution of the Islamic Republic of Iran"Tehran puzzled by forged 'riots' letter""Iran and its minorities: Down in the second class""Iran: Handling Of Ahvaz Unrest Could End With Televised Confessions""Bombings Rock Iran Ahead of Election""Five die in Iran ethnic clashes""Iran: Need for restraint as anniversary of unrest in Khuzestan approaches"Archived"Iranian Sunni protesters killed in clashes with security forces"Archived

                                          Can't initialize raids on a new ASUS Prime B360M-A motherboard2019 Community Moderator ElectionSimilar to RAID config yet more like mirroring solution?Can't get motherboard serial numberWhy does the BIOS entry point start with a WBINVD instruction?UEFI performance Asus Maximus V Extreme