Minimum positive missing integer from given array

Question

I want to find minimum positive integer missing from an array with 'n' time complexity. Is it possible? E.g let {-3,-6,1,-9,4,6,0} is our array then minimum positive integer would be 2.

You just want a language-agnostic algorithm? Or do you want help with an implementation in a specific language? Please edit your question to tag accordingly. But even if you want a language-agnostic (which is a valid tag) algorithm (also a valid tag) you still have to tell us what you have tried, what you have researched, and show us that you have spent some effort on the issue. — Some programmer dude
– Some programmer dude, Commented May 30, 2018 at 12:29

Hein Wessels · Accepted Answer · 2018-05-30 16:11:38Z

1

How about creating another array to store which variables you have found. In this array the number can be its index, and if it has been found stored as a boolean. Then you look through that array to see which one wasnt found. Your description is quite vage, so I might not solve it exactly, but it might get you closer.

bool arr_check [ARR_SIZE];    // whick numbers has been found.
for (int i=0; i<ARR_SIZE; i++)
    if(arr[i]>0)
        arr_check[arr[i]] = true;
for (int i=0; i<ARR_SIZE; i++)
    if (!arr_check[i])
        return i;

You will only have to scan through a array twice, which gives it complexity '2N', right? You won't get it must faster without sorting it first, which is more than "N"

edited May 30, 2018 at 16:11

answered May 30, 2018 at 12:30

Hein Wessels

9475 silver badges15 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Akshay Over a year ago

this will give you the smallest positive integer from your array, but we have to find the smallest missing positive integer. You can check the example

Hein Wessels Over a year ago

Ah, sorry, I adapted my answer. Hope this is what you need.

Collectives™ on Stack Overflow

Minimum positive missing integer from given array

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related