Find Smallest Missing Positive Number-By Negating Array Elements

First, all positive integers should be migrated to the left side of the array. We next traverse over this left segment and negating the value at index (x – 1) marks the occurrences of every number x. Finally, go over the left segment once more and, looking for the first unmarked piece, determine the missing number.

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.

C++

// C++ program to find the smallest positive missing number 
// by negating the array elements

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

// Function to partition the array into positive and
// non-positive subarrays
int partition(vector<int> &arr) {
    int pivotIdx = 0;
    int n = arr.size();

    for (int i = 0; i < n; i++) {
        
        // Move positive elements to the left
        if (arr[i] > 0) {
            swap(arr[i], arr[pivotIdx]);
            pivotIdx++;
        }
    }

    // return index of the first non-positive number
    return pivotIdx;
}

// Function for finding the first missing positive number
int missingNumber(vector<int> &arr) {
    int k = partition(arr);

    // Traverse the positive part of the array
    for (int i = 0; i < k; i++) {
        
        // Find the absolute value to get the original number
        int val = abs(arr[i]);

        // If val is within range, then mark the element at
        // index val-1 to negative
        if (val - 1 < k && arr[val - 1] > 0) {
            arr[val - 1] = -arr[val - 1];
        }
    }

    // Find first unmarked index
    for (int i = 0; i < k; i++) {
        if (arr[i] > 0) {
            return i + 1;
        }
    }

    // If all numbers from 1 to k are marked
    // then missing number is k + 1
    return k + 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 negating the array elements
#include <stdio.h>

// Function to partition the array into positive and
// non-positive subarrays
int partition(int *arr, int n) {
    int pivotIdx = 0;

    for (int i = 0; i < n; i++) {
        
        // Move positive elements to the left
        if (arr[i] > 0) {
            int temp = arr[i];
            arr[i] = arr[pivotIdx];
            arr[pivotIdx] = temp;
            pivotIdx++;
        }
    }

    // return index of the first non-positive number
    return pivotIdx;
}

// Function for finding the first missing positive number
int missingNumber(int *arr, int n) {
    int k = partition(arr, n);

    // Traverse the positive part of the array
    for (int i = 0; i < k; i++) {
        
        // Find the absolute value to get the original number
        int val = abs(arr[i]);

        // If val is within range, then mark the element at
        // index val-1 to negative
        if (val - 1 < k && arr[val - 1] > 0) {
            arr[val - 1] = -arr[val - 1];
        }
    }

    // Find first unmarked index
    for (int i = 0; i < k; i++) {
        if (arr[i] > 0) {
            return i + 1;
        }
    }

    // If all numbers from 1 to k are marked then
    // missing number is k + 1
    return k + 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 smallest positive missing number 
// by negating the array elements

import java.util.Arrays;

class GfG {

    // Function to partition the array into positive and
    // non-positive subarrays
    static int partition(int[] arr) {
        int pivotIdx = 0;
        int n = arr.length;

        for (int i = 0; i < n; i++) {
            
            // Move positive elements to the left
            if (arr[i] > 0) {
                int temp = arr[i];
                arr[i] = arr[pivotIdx];
                arr[pivotIdx] = temp;
                pivotIdx++;
            }
        }

        // return index of the first non-positive number
        return pivotIdx;
    }

    // Function for finding the first missing positive number
    static int missingNumber(int[] arr) {
        int k = partition(arr);

        // Traverse the positive part of the array
        for (int i = 0; i < k; i++) {
            
            // Find the absolute value to get the original number
            int val = Math.abs(arr[i]);

            // If val is within range, then mark the element at
            // index val-1 to negative
            if (val - 1 < k && arr[val - 1] > 0) {
                arr[val - 1] = -arr[val - 1];
            }
        }

        // Find first unmarked index
        for (int i = 0; i < k; i++) {
            if (arr[i] > 0) {
                return i + 1;
            }
        }

        // If all numbers from 1 to k are marked
        // then missing number is k + 1
        return k + 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 negating the array elements

def partition(arr):
    pivotIdx = 0
    n = len(arr)

    for i in range(n):
        
        # Move positive elements to the left
        if arr[i] > 0:
            arr[i], arr[pivotIdx] = arr[pivotIdx], arr[i]
            pivotIdx += 1

    # return index of the first non-positive number
    return pivotIdx

# Function for finding the first missing positive number
def missingNumber(arr):
    k = partition(arr)

    # Traverse the positive part of the array
    for i in range(k):
        
        # Find the absolute value to get the original number
        val = abs(arr[i])

        # If val is within range, then mark the element at
        # index val-1 to negative
        if val - 1 < k and arr[val - 1] > 0:
            arr[val - 1] = -arr[val - 1]

    # Find first unmarked index
    for i in range(k):
        if arr[i] > 0:
            return i + 1

    # If all numbers from 1 to k are marked
    # then missing number is k + 1
    return k + 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 negating the array elements

// Function to partition the array into positive and
// non-positive subarrays
function partition(arr) {
    let pivotIdx = 0;
    const n = arr.length;

    for (let i = 0; i < n; i++) {
        
        // Move positive elements to the left
        if (arr[i] > 0) {
            [arr[i], arr[pivotIdx]] = [arr[pivotIdx], arr[i]];
            pivotIdx++;
        }
    }

    // return index of the first non-positive number
    return pivotIdx;
}

// Function for finding the first missing positive number
function missingNumber(arr) {
    const k = partition(arr);

    // Traverse the positive part of the array
    for (let i = 0; i < k; i++) {
        
        // Find the absolute value to get the original number
        const val = Math.abs(arr[i]);

        // If val is within range, then mark the element at
        // index val-1 to negative
        if (val - 1 < k && arr[val - 1] > 0) {
            arr[val - 1] = -arr[val - 1];
        }
    }

    // Find first unmarked index
    for (let i = 0; i < k; i++) {
        if (arr[i] > 0) {
            return i + 1;
        }
    }

    // If all numbers from 1 to k are marked
    // then missing number is k + 1
    return k + 1;
}

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

Output

3