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 section once more and, looking for the first unmarked piece, determine the missing number.
Alternate Approach] By Marking Indices – O(n) Time and O(1) Space
The goal is to identify the smallest positive number absent from an unsorted array arr[] including both positive and negative items.
Note: You have original array modification power.
Illustrations:
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.
By Negating Array Elements – O(n) Time and O(1) Space
Should our array consist entirely of positive numbers, we can record the presence of a number x by negating the number at index x – 1 in the array. We can thus find our first missing element by first looking for the first unmarked element in the same array.
Moving all the positive integers to the left side of the array will help us to apply this method for an array comprising both positive and negative numbers. After this is finished, we may use the positive array technique on this left side—an array of positive numbers.
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))C#
// C# program to find the smallest positive missing number
// by negating the array elements
using System;
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;
}
static void Main() {
int[] arr = { 2, -3, 4, 1, 1, 7 };
Console.WriteLine(MissingNumber(arr));
}
}JavaScript
// 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