Find Smallest Missing Positive Number

/ DSA / By
Spread the love
Find Smallest Missing Positive Number

The objective is to determine the smallest positive number that is absent from an unsorted array arr[] that contains both positive and negative items.

Note: The initial array is modifiable.

Examples:

Input: arr[] = {2, -3, 4, 1, 1, 7}
Output: 3
Explanation: 3 is the smallest positive number missing from the array.

Input: arr[] = {5, 3, 2, 5, 1}
Output: 4
Explanation: 4 is the smallest positive number missing from the array.

Input: arr[] = {-8, 0, -1, -4, -3}
Output: 1
Explanation: 1 is the smallest positive number missing from the array.

Table of Content

[Naive approach] By Sorting – O(n*log n) Time and O(n) Space

Sorting the array will help one to presume a missing number as 1. Now go over the array iteratively and for every element arr[i],

Should arr[i] be a missing number, increase missing number by one.
Proceed to hunt for the missing number if arr[i] < missing number.
Should arr[i] surpass the missing number, break and provide the missing number back.

C++

// C++ program to find the first positive missing number 
// using Sorting

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// Function to find the first positive missing number
int missingNumber(vector<int> &arr) {
    sort(arr.begin(), arr.end());
    int res = 1;
    for (int i = 0; i < arr.size(); i++) {

        // If we have found 'res' in the array,
        // 'res' is no longer missing, so increment it
        if (arr[i] == res) 
            res++;

        // If the current element is larger than 'res',
        // 'res' cannot be found in the array,
        // so it is our final answer
        else if (arr[i] > res) 
            break;
    }
    return res;
}

int main() {
    vector<int> arr = {2, -3, 4, 1, 1, 7};

    cout << missingNumber(arr);
    return 0;
}

C

// C program to find the first positive missing number 
// using Sorting
#include <stdio.h>

int cmp(const int *a, const int *b) {
    return (*a - *b);
}

// Function to find the first positive missing number
int missingNumber(int arr[], int size) {
    
    // sort the array
    qsort(arr, size, sizeof(int), (int(*)(const void*, const void*))cmp);

    // res will hold the current smallest missing number,
    // initially set to 1
    int res = 1;
    for (int i = 0; i < size; i++) {

        // If we have found 'res' in the array,
        // 'res' is no longer missing, so increment it
        if (arr[i] == res) {
            res++;
        }

        // If the current element is larger than 'res',
        // 'res' cannot be found in the array,
        // so it is our final answer
        else if (arr[i] > res) {
            break;
        }
    }
    return res;
}

int main() {
    int arr[] = {2, -3, 4, 1, 1, 7};
    int size = sizeof(arr) / sizeof(arr[0]);

    printf("%d", missingNumber(arr, size));
    return 0;
}

Java

// Java program to find the first positive missing number 
// using Sorting
import java.util.Arrays;
class GfG {
    
    // Function to find the first positive missing number
    static int missingNumber(int[] arr) {
        Arrays.sort(arr);

        // res will hold the current smallest missing number,
        // initially set to 1
        int res = 1;
        for (int i = 0; i < arr.length; i++) {

            // If we have found 'res' in the array,
            // 'res' is no longer missing, so increment it
            if (arr[i] == res) {
                res++;
            }

            // If the current element is larger than 'res',
            // 'res' cannot be found in the array,
            // so it is our final answer
            else if (arr[i] > res) {
                break;
            }
        }
        return res;
    }

    public static void main(String[] args) {
        int[] arr = {2, -3, 4, 1, 1, 7};
        System.out.println(missingNumber(arr));
    }
}

Python

# C++ program to find the first positive missing number 
# using Sorting

# Function to find the first positive missing number
def missingNumber(arr):
    arr.sort()

    # res will hold the current smallest missing number,
    # initially set to 1
    res = 1
    for num in arr:

        # If we have found 'res' in the array,
        # 'res' is no longer missing, so increment it
        if num == res:
            res += 1

        # If the current element is larger than 'res',
        # 'res' cannot be found in the array,
        # so it is our final answer
        elif num > res:
            break
    return res


if __name__ == "__main__":

    arr = [2, -3, 4, 1, 1, 7]
    print(missingNumber(arr))

JS

// JavaScript program to find the first positive missing number 
// using Sorting

// Function to find the first positive missing number
function missingNumber(arr) {
    arr.sort((a, b) => a - b);

    // ans will hold the current smallest missing number,
    // initially set to 1
    let res = 1;
    for (let i = 0; i < arr.length; i++) {

        // If we have found 'res' in the array,
        // 'res' is no longer missing, so increment it
        if (arr[i] == res) {
            res++;
        }

        // If the current element is larger than 'res',
        // 'res' cannot be found in the array,
        // so it is our final answer
        else if (arr[i] > res) {
            break;
        }
    }
    return res;
}

const arr = [2, -3, 4, 1, 1, 7];
console.log(missingNumber(arr));

Output

3