Finding the smallest positive number

Question

Question: Smallest Positive missing number

What is wrong with this code?

class Solution
{
    public:
    //Function to find the smallest positive number missing from the array.
    int missingNumber(int arr[], int n) 
    { 
        // Your code here
        sort(arr,arr+n);
        int index=1;
        int a;
        for(int i=0;i<n;i++){
            if(arr[i]>0){
                if(arr[i]!=index){
                    a=index;
                    break;
                }
                else{
                    index++;
                }
            }
        }
        return index;
    } 
};

Answer 1

In every iteration your i is increasing, so this condition which you have written in your for loop:

arr[i]!=index

Here, let's say if the input array has duplicate elements, then for 2 consecutive values of i you will get the same value in arr[i]. In the first comparison, this condition will hold false, so you go to the else part and increment the index value. In the next iteration, your condition arr[i]!=index is always going to be true, as arr[i] is still the same but the index is increased. Thus your program will break from the for loop and the index value is getting returned. That is where it's failing.

So, it will always fail whenever you have duplicate positive elements in your input array. Except for the case when the largest item in the array is the only duplicate in input.

Answer 2

Here's one hint:

    for(int i=0;i<n;i++){
        if(arr[i]>0){
            if(arr[i]!=index){
                a=index;
                break;
            }
            else{
                index++;
            }
        }
    }

imagine your sorted array is [-10, -5, 0, 1, 2, 3, 4, 5]

When i==3. arr[3] is equal 1, which is the first number you want to evaluate against index. But index will be equal to 3, not 1 as you might have intended.

And as others have pointed out - duplicate numbers in the array are not handled either.

Second hint:

What if I told you... that there was a way to solve this problem without having to sort the input array at all? What if you had an allocated an array of bools of length N to work with....

Answer 3

You should only increase index if arr[i] == index or else you'll get the wrong result for arrays with duplicates, like {1,2,3,4,5,5,6,7}.

int missingNumber(int arr[], int n) { 
    std::sort(arr,arr + n);

    int index=1;
    int a;
    for(int i=0; i < n; i++) { 
        if(arr[i] > 0) {
            if(arr[i] == index) {       // equal, step
                ++index;
            } else if(arr[i] > index) { // greater, we found the missing one
                a=index;
                break;
            }                           // else, arr[i] == index - 1, don't step
        }
    }
    return index;
}

You are missing a great opportunity to use the sorted array though. Since you're only interested in positive numbers, you can use std::upper_bound to find the first positive number. This search is done very efficiently and it also means that you don't have to check if(arr[i] > 0) in every iteration of your loop.

Example:

int missingNumber(int arr[], int n) { 
    int* end = arr + n;

    std::sort(arr, end);        
    int* it = std::upper_bound(arr, end, 0); // find the first number greater than 0

    int expected = 1;
    
    while(it != end && *it <= expected) {
        if(*it == expected) ++expected;
        ++it;
    }
    
    return expected;
}

Alternatively, std::partition the array to put the positve numbers first in the array even before you sort it. That means that you'll not waste time sorting non-positive numbers.

int missingNumber(int arr[], int n) { 
    int* end = arr + n;

    end = std::partition(arr, end, [](int x){ return x > 0; });
    std::sort(arr, end);        

    int expected = 1;
    
    for(int* it = arr; it != end && *it <= expected; ++it) {
        if(*it == expected) ++expected;
    }

    return expected;
}

Answer 4

You can try using a counting array and then walk the array until you come to an empty space.

int main() {
    int N;
    cin >> N;
    int num; // set to zero b/c zero is out lowest possible number
    vector<int> numbers;
    while (cin >> num) {
        numbers.push_back(num); 
    }

   //create a counting array to add a 1 to all the positions that exist
    int * cA = new int[10000] {0};
    
    for (int i = 0; i < N; i++) {
        if (numbers[i] >= 0) {
            cA[numbers[i]]++;
        }
    }
    
    for (int i = 1; i < 10000; i++) {
        if (cA[i] == 0) {
            num = i;
            break;
        }
    }
    cout << num;
    
    delete []cA;
    
    return 0;
}

Answer 5

How Code Works : first get element count and add all items into Vector by Loop,with second loop going to 1000 i check from 1 to 1000 if any of 1,2,3,4,... is not in the vector i print missing,i do this with bool variable res,if any of loop counter starting from 1 to 1000 is in the vector res variable is set to True otherwise False.be careful in each run of For Loop from 1 to 1000 you should set res=False

#include <iostream>
#include <vector>
using namespace std;
//Programmer : Salar Ashgi
int main()
{
    vector<int> v;
    int k=0;
    cout<<"Enter array count ?\n";
    cin>>k;
    int n;
    for(int i=0;i<k;i++)
    {
        cout<<"Enter num "<<i+1<<" : ";
        cin>>n;
        v.push_back(n);
    }
bool res=false;
for(int i=1;i<=1000;i++)
{
    res=false;
    for(int j=0;j<k;j++)
    {
        if(v[j]==i)
        {
            res=true;
            break;
        }
        
    }
    if(!res)
    {
        cout<<i<<" is missing !";
        break;
    }
        
    
}
    
}