Find Smallest Missing Positive Number-By Marking Indices

The concept is to note the presence of elements inside the same array. Since 1 is the smallest positive integer, first we look to see whether 1 is there; should it be absent, the response is 1. All numbers that are either negative or greater than the array size are converted to 1 otherwise to maintain all numbers within a range of 1 to n.

We next index the numbers using their values. To indicate the presence of a number x, we are adding n to the number existing at index x – 1. At last, we search the array for the first unmarked index to obtain the smallest missing positive value.

C++

// C++ program to find the smallest positive missing number 
// by marking indices 

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

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

    // Check if 1 is present in array or not
    for (int i = 0; i < n; i++) {
        if (arr[i] == 1) {
            flag = true;
            break;
        }
    }

    // If 1 is not present
    if (flag == false)
        return 1;

    // Change out of range values to 1
    for (int i = 0; i < n; i++) {
        if (arr[i] <= 0 || arr[i] > n)
            arr[i] = 1;
    }

    // Mark the occurrence of numbers 
      // directly within the same array
    for (int i = 0; i < n; i++) {
        arr[(arr[i] - 1) % n] += n;
    }

    // Finding which index has value less than n
    for (int i = 0; i < n; i++) {
        if (arr[i] <= n)
            return i + 1;
    }

    // If array has values from 1 to n
    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 smallest positive missing number 
// by marking indices

#include <stdio.h>

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

    // Check if 1 is present in array or not
    for (int i = 0; i < n; i++) {
        if (arr[i] == 1) {
            flag = 1;
            break;
        }
    }

    // If 1 is not present
    if (flag == 0)
        return 1;

    // Change out of range values to 1
    for (int i = 0; i < n; i++) {
        if (arr[i] <= 0 || arr[i] > n)
            arr[i] = 1;
    }

    // Mark the occurrence of numbers 
    // directly within the same array
    for (int i = 0; i < n; i++) {
        arr[(arr[i] - 1) % n] += n;
    }

    // Finding which index has value less than n
    for (int i = 0; i < n; i++) {
        if (arr[i] <= n)
            return i + 1;
    }

    // If array has values from 1 to n
    return n + 1;
}

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

Java

// Java program to find the smallest positive missing number 
// by marking indices

import java.util.*;
class GfG {

    // Function for finding the first missing positive number
    static int missingNumber(int[] arr) {
        int n = arr.length;
        boolean flag = false;

        // Check if 1 is present in array or not
        for (int i = 0; i < n; i++) {
            if (arr[i] == 1) {
                flag = true;
                break;
            }
        }

        // If 1 is not present
        if (!flag)
            return 1;

        // Change out of range values to 1
        for (int i = 0; i < n; i++) {
            if (arr[i] <= 0 || arr[i] > n)
                arr[i] = 1;
        }

        // Mark the occurrence of numbers 
        // directly within the same array
        for (int i = 0; i < n; i++) {
            arr[(arr[i] - 1) % n] += n;
        }

        // Finding which index has value less than n
        for (int i = 0; i < n; i++) {
            if (arr[i] <= n)
                return i + 1;
        }

        // If array has values from 1 to n
        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 smallest positive missing number 
# by marking indices

# Function for finding the first missing positive number
def missingNumber(arr):
    n = len(arr)
    flag = False

    # Check if 1 is present in array or not
    for i in range(n):
        if arr[i] == 1:
            flag = True
            break

    # If 1 is not present
    if not flag:
        return 1

    # Change out of range values to 1
    for i in range(n):
        if arr[i] <= 0 or arr[i] > n:
            arr[i] = 1

    # Mark the occurrence of numbers 
    # directly within the same array
    for i in range(n):
        arr[(arr[i] - 1) % n] += n

    # Finding which index has value less than n
    for i in range(n):
        if arr[i] <= n:
            return i + 1

    # If array has values from 1 to n
    return n + 1

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

JS

// JavaScript program to find the smallest positive missing number 
// by marking indices

// Function for finding the first missing positive number
function missingNumber(arr) {
    let n = arr.length;
    let flag = false;

    // Check if 1 is present in array or not
    for (let i = 0; i < n; i++) {
        if (arr[i] === 1) {
            flag = true;
            break;
        }
    }

    // If 1 is not present
    if (!flag) return 1;

    // Change out of range values to 1
    for (let i = 0; i < n; i++) {
        if (arr[i] <= 0 || arr[i] > n) arr[i] = 1;
    }

    // Mark the occurrence of numbers 
    // directly within the same array
    for (let i = 0; i < n; i++) {
        arr[(arr[i] - 1) % n] += n;
    }

    // Finding which index has value less than n
    for (let i = 0; i < n; i++) {
        if (arr[i] <= n) return i + 1;
    }

    // If array has values from 1 to n
    return n + 1;
}

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

Output

3