Find all numbers in range [1, N] that are not present in given Array

0 0 3 minutes read

Given an array arr[] of size N, where arr[i] is natural numbers less than or equal to N, the task is to find all the numbers in the range [1, N] that are not present in the given array.

Examples:

Input: arr[ ] = {5, 5, 4, 4, 2}
Output: 1 3
Explanation:
For all numbers in the range [1, 5], 1 and 3 are not present in the array.

Input: arr[ ] = {3, 2, 3, 1}
Output: 4

Naive Approach: The simplest approach is to hash every array element using any data structure like the dictionary and then iterate over the range [1, N] and print all numbers not present in the hash.

Time Complexity: O(N)
Auxiliary Space: O(N)

Approach: The above approach can be optimized further by marking the number at position arr[i] – 1, negative to mark i is present in the array. Then print all positions of the array elements that are positive as they are missing. Follow the steps below to solve the problem:

Iterate over the array, arr[] and for each current element, num perform the following steps:
- Update arr[abs(num)-1] to -abs(arr[abs(num)-1]).
Iterate over the array, arr[] using the variable i, and print the i+1 if arr[i] is positive.

Below is the implementation of the above approach:

C++

// C++ program for above approach 
#include <iostream> 
using namespace std; 
  
// Function to find the missing numbers 
void getMissingNumbers(int arr[], int N) 
{ 
    // traverse the array arr[] 
    for (int i = 0; i < N; i++) { 
        // Update 
        arr[abs(arr[i]) - 1] = -(abs(arr[abs(arr[i]) - 1])); 
    } 
    // Traverse the array arr[] 
    for (int i = 0; i < N; i++) { 
        // If Num is not present 
        if (arr[i] > 0) 
            cout << i + 1 << " "; 
    } 
} 
  
// Driver Code 
int main() 
{ 
  
    // Given Input 
    int N = 5; 
    int arr[] = { 5, 5, 4, 4, 2 }; 
  
    // Function Call 
    getMissingNumbers(arr, N); 
    return 0; 
} 
// This codeis contributed by dwivediyash

Java

// Java program for the above approach 
import java.io.*; 
  
class GFG  
{ 
    
    // Function to find the missing numbers 
    static void getMissingNumbers(int arr[], int N) 
    { 
        
        // traverse the array arr[] 
        for (int i = 0; i < N; i++)  
        { 
            
            // Update 
            arr[(Math.abs(arr[i]) - 1)] 
                = -(Math.abs(arr[(Math.abs(arr[i]) - 1)])); 
        } 
        
        // Traverse the array arr[] 
        for (int i = 0; i < N; i++)  
        { 
            
            // If Num is not present 
            if (arr[i] > 0) 
                System.out.print(i + 1 + " "); 
        } 
    } 
  
    // Driver Code 
    public static void main(String[] args) 
    { 
        
        // Given Input 
        int N = 5; 
        int arr[] = { 5, 5, 4, 4, 2 }; 
  
        // Function Call 
        getMissingNumbers(arr, N); 
    } 
} 
  
// This code is contributed by Potta Lokesh

Python3

# Python program for the above approach 
  
# Function to find the missing numbers 
def getMissingNumbers(arr): 
  
    # Traverse the array arr[] 
    for num in arr: 
  
        # Update 
        arr[abs(num)-1] = -(abs(arr[abs(num)-1])) 
  
    # Traverse the array arr[] 
    for pos, num in enumerate(arr): 
  
        # If Num is not present 
        if num > 0: 
            print(pos + 1, end =' ') 
  
  
# Given Input 
arr = [5, 5, 4, 4, 2] 
  
# Function Call 
getMissingNumbers(arr) 

C#

// C# program for above approach 
using System; 
using System.Collections.Generic; 
  
class GFG{ 
  
// Function to find the missing numbers 
static void getMissingNumbers(int []arr, int N) 
{ 
    
    // traverse the array arr[] 
    for (int i = 0; i < N; i++)  
    { 
        
        // Update 
        arr[(Math.Abs(arr[i]) - 1)] = -(Math.Abs(arr[(Math.Abs(arr[i]) - 1)])); 
    } 
    
    // Traverse the array arr[] 
    for (int i = 0; i < N; i++) 
    { 
        
        // If Num is not present 
        if (arr[i] > 0) 
          Console.Write(i + 1 + " "); 
    } 
} 
  
// Driver Code 
public static void Main() 
{ 
  
    // Given Input 
    int N = 5; 
    int []arr = { 5, 5, 4, 4, 2 }; 
  
    // Function Call 
    getMissingNumbers(arr, N); 
} 
} 
  
// This code is contributed by ipg2016107.

Javascript

<script> 
// Javascript program for the above approach 
  
// Function to find the missing numbers 
function getMissingNumbers(arr){ 
  
    // Traverse the array arr[] 
    for(let num of arr) 
        // Update 
        arr[(Math.abs(num)-1)] = -(Math.abs(arr[(Math.abs(num)-1)])) 
  
    // Traverse the array arr[] 
    for (pos in arr) 
  
        // If Num is not present 
        if(arr[pos] > 0) 
            document.write(`${parseInt(pos) + 1} `) 
} 
  
// Given Input 
let arr = [5, 5, 4, 4, 2] 
  
// Function Call 
getMissingNumbers(arr) 
  
// This code is contributed by _saurabh_jaiswal. 
</script>

Output

1 3

Time Complexity: O(N)
Auxiliary Space: O(1)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!