Find Smallest Missing Positive Number-Using Cycle Sort

The concept is like Cycle Sort and moves every element in the array to its proper place depending on its value. Thus, for any number, say x, arrange 1 ≤ x ≤ n at the (x – 1)th index.

At last, go over the array looking for whether the numbers match the predicted indexes or not. The first missing positive number results from the first spot where the number does not match its index. The smallest missing positive integer is n + 1, if all the numbers from 1 to n match their proper indices.

C++

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

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

// Function for finding the first missing positive number
int missingNumber(vector<int> &arr) {
    int n = arr.size();
    for (int i = 0; i < n; i++) {

        // if arr[i] is within range [1, n] and arr[i] is
        // not placed at (arr[i]-1)th index in arr
        while (arr[i] >= 1 && arr[i] <= n
               && arr[i] != arr[arr[i] - 1]) {
                   
            // then swap arr[i] and arr[arr[i]-1]
            // to place arr[i] to its corresponding index
            swap(arr[i], arr[arr[i] - 1]);
        }
    }

    // If any number is not at its corresponding index 
    // then it is the missing number
    for (int i = 1; i <= n; i++) {
        if (i != arr[i-1]) {
            return i;
        }
    }

    // If all number from 1 to n are present 
    // then n + 1 is smallest missing number
    return n + 1;
}

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

C

// C program to find the first missing positive number 
// using cycle sort

#include <stdio.h>

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// Function for finding the first missing positive number
int missingNumber(int arr[], int n) {
    for (int i = 0; i < n; i++) {

        // if arr[i] is within range [1, n] and arr[i] is
        // not placed at (arr[i]-1)th index in arr
        while (arr[i] >= 1 && arr[i] <= n 
               && arr[i] != arr[arr[i] - 1]) {
                   
            // then swap arr[i] and arr[arr[i]-1]
            // to place arr[i] to its corresponding index
            swap(&arr[i], &arr[arr[i] - 1]);
        }
    }

    // If any number is not at its corresponding index 
    // then it is the missing number
    for (int i = 1; i <= n; i++) {
        if (i != arr[i-1]) {
            return i;
        }
    }

    // If all number from 1 to n are present 
    // then n + 1 is smallest missing number
    return n + 1;
}

int main() {
    int arr[] = {2, -3, 4, 1, 1, 7};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("%d\n", missingNumber(arr, n));
    return 0;
}

Java

// Java program to find the first missing positive number 
// using cycle sort
import java.util.*;
class GfG {

    // Function for finding the first missing positive number
    static int missingNumber(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n; i++) {

            // if arr[i] is within the range [1, n] and arr[i]
            // is not placed at (arr[i]-1)th index in arr
            while (arr[i] >= 1 && arr[i] <= n
                   && arr[i] != arr[arr[i] - 1]) {

                // then swap arr[i] and arr[arr[i]-1] to
                // place arr[i] to its corresponding index
                int temp = arr[i];
                arr[i] = arr[arr[i] - 1];
                arr[temp - 1] = temp;
            }
        }

        // If any number is not at its corresponding index 
        // then it is the missing number
        for (int i = 1; i <= n; i++) {
            if (i != arr[i - 1]) {
                return i;
            }
        }

        // If all number from 1 to n are present then n+1 
        // is smallest missing number
        return n + 1;
    }

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

Python

# Python program to find the first missing positive number 
# using cycle sort


# Function for finding the first
# missing positive number
def missingNumber(arr):
    n = len(arr)
    for i in range(n):

        # if arr[i] is within the range 1 to n
        # and arr[i] is not placed at (arr[i]-1)th index in arr
        while 1 <= arr[i] <= n and arr[i] != arr[arr[i] - 1]:

            # then swap arr[i] and arr[arr[i]-1] to place arr[i]
            # to its corresponding index
            temp = arr[i]
            arr[i] = arr[arr[i] - 1]
            arr[temp - 1] = temp

    # If any number is not at its corresponding index, then it
    # is the missing number
    for i in range(1, n + 1):
        if i != arr[i - 1]:
            return i

    # If all number from 1 to n are present 
    # then n + 1 is smallest missing number
    return n + 1


if __name__ == '__main__':
    arr = [2, -3, 4, 1, 1, 7]
    print(missingNumber(arr))

JS

// JavaScript program to find the first missing positive number 
// using cycle sort

function missingNumber(arr) {
    let n = arr.length;
    for (let i = 0; i < n; i++) {

        // if arr[i] is within the range 1 to n and arr[i] is
        // not placed at (arr[i]-1)th index in arr
        while (arr[i] >= 1 && arr[i] <= n 
               && arr[i] !== arr[arr[i] - 1]) {

            // then swap arr[i] and arr[arr[i]-1] to place 
            // arr[i] to its corresponding index
            let temp = arr[i];
            arr[i] = arr[arr[i] - 1];
            arr[temp - 1] = temp;
        }
    }

    // If any number is not at its corresponding index 
    // it is then missing,
    for (let i = 1; i <= n; i++) {
        if (i !== arr[i - 1]) {
            return i;
        }
    }

    // If all number from 1 to n are present 
    // then n+1 is smallest missing number
    return n + 1;
}

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

Output

3