Fill the missing numbers in the array of N natural numbers such that arr[i] not equal to i

0 0 7 minutes read

Given an unsorted array arr[] consisting of N natural numbers and the missing numbers as 0 such that arr[i] ? i, the task is to find and fill these missing numbers without changing the initial order. Please note that the array can contain numbers from 1 to N only once.

Examples:

Input: arr[] = {7, 4, 0, 3, 0, 5, 1}
Output: 7 4 6 3 2 5 1
Explanation:
In the given array, unfilled indices are 2 and 4. So the missing numbers that can be filled, to fulfil the criteria arr[i] ? i, are 6 and 2 respectively.

Input: arr[] = {2, 1, 0, 0, 0}
Output: 2 1 4 5 3
Explanation:
In the given array unfilled indices are 3, 4 and 5. So the missing numbers that can be filled, to fulfil the criteria arr[i] ? i, are 4, 5 and 3 respectively.

Approach:

Store all the unfilled indices in an array unfilled_indices[]. i.e, for all i such that arr[i] = 0.
Also store all the elements which are missing in the array missing[]. This can be done by first inserting all elements from 1 to N and then deleting all elements which is not 0
Simply iterate the unfilled_indices[] array and start allocating all elements stored in missing[] array possibly taking each element from backwards(to avoid any i getting arr[i] = i).
Now it may be possible that maximum one index can get the same arr[i] = i. Simply swap with it any other element after checking that the other index should be present in unfilled_indices[].
Print the new array.

Below is the implementation of the above approach:

C++

// C++ implementation of above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to print array
void printArray(int[], int);
 
// Function to fill the position
// with arr[i] = 0
void solve(int arr[], int n)
{
 
    set<int> unfilled_indices;
    set<int> missing;
 
    // Inserting all elements in
    // missing[] set from 1 to N
    for (int i = 1; i < n; i++)
        missing.insert(i);
 
    for (int i = 1; i < n; i++) {
 
        // Inserting unfilled positions
        if (arr[i] == 0)
            unfilled_indices.insert(i);
 
        // Removing allocated_elements
        else {
            auto it = missing.find(arr[i]);
            missing.erase(it);
        }
    }
    auto it2 = missing.end();
    it2--;
 
    // Loop for filling the positions
    // with arr[i] != i
    for (auto it = unfilled_indices.begin();
         it != unfilled_indices.end();
         it++, it2--) {
        arr[*it] = *it2;
    }
    int pos = 0;
 
    // Checking for any arr[i] = i
    for (int i = 1; i < n; i++) {
        if (arr[i] == i) {
            pos = i;
        }
    }
 
    int x;
 
    // Finding the suitable position
    // in the array to swap with found i
    // for which arr[i] = i
    if (pos != 0) {
        for (int i = 1; i < n; i++) {
            if (pos != i) {
 
                // Checking if the position
                // is present in unfilled_position
                if (unfilled_indices.find(i)
                    != unfilled_indices.end()) {
 
                    // Swapping arr[i] & arr[pos]
                    // (arr[pos] = pos)
                    x = arr[i];
                    arr[i] = pos;
                    arr[pos] = x;
                    break;
                }
            }
        }
    }
    printArray(arr, n);
}
 
// Function to Print the array
void printArray(int arr[], int n)
{
    for (int i = 1; i < n; i++)
        cout << arr[i] << " ";
}
 
// Driver Code
int main()
{
    int arr[] = { 0, 7, 4, 0,
                  3, 0, 5, 1 };
 
    int n = sizeof(arr) / sizeof(arr[0]);
 
    solve(arr, n);
    return 0;
}

Java

// Java implementation of above approach
import java.io.*;
import java.util.*; 
class GFG 
{
 
  // Function to fill the position
  // with arr[i] = 0
  static void solve(int arr[], int n)
  {
    Set<Integer> unfilled_indices = new HashSet<Integer>();
    Set<Integer> missing = new HashSet<Integer>();
 
    // Inserting all elements in
    // missing[] set from 1 to N
    for (int i = 1; i < n; i++)
    {
      missing.add(i);
    }
    for (int i = 1; i < n; i++)
    {
 
      // Inserting unfilled positions
      if (arr[i] == 0)
      {
        unfilled_indices.add(i);
      }
 
      // Removing allocated_elements
      else
      {
        missing.remove(arr[i]);
      }
    }
    int[] mi = new int[missing.size()];
    int l = 0;
    for(int x:missing)
    {
      mi[l++] = x;
    }
    int m = missing.size();
 
    // Loop for filling the positions
    // with arr[i] != i
    for(int it:unfilled_indices)
    {
      arr[it] = mi[m - 1];
      m--;
    }
    int pos = 0;
 
    // Checking for any arr[i] = i
    for (int i = 1; i < n; i++)
    {
      if (arr[i] == i)
      {
        pos = i;
      }
    }
    int x;
 
    // Finding the suitable position
    // in the array to swap with found i
    // for which arr[i] = i
    if (pos != 0)
    {
      for (int i = 1; i < n; i++)
      {
        if (pos != i)
        {
 
          // Checking if the position
          // is present in unfilled_position
          if(unfilled_indices.contains(i))
          {
 
            // Swapping arr[i] & arr[pos]
            // (arr[pos] = pos)
            x = arr[i];
            arr[i] = pos;
            arr[pos] = x;
            break;
          }
        }
      }
    }
    printArray(arr, n);
  }
 
  // Function to Print the array
  static void printArray(int arr[], int n)
  {
    for (int i = 1; i < n; i++)
    {
      System.out.print(arr[i] + " ");    
    }
  }
 
  // Driver Code
  public static void main (String[] args)
  {
    int[] arr = { 0, 7, 4, 0,3, 0, 5, 1 };
    int n = arr.length;
    solve(arr, n);
  }
}
 
// This code is contributed by avanitrachhadiya2155

Python3

# Python3 implementation of above approach
 
# Function to fill the position
# with arr[i] = 0
def solve(arr, n):
     
    unfilled_indices = {}
    missing = {}
     
    # Inserting all elements in
    # missing[] set from 1 to N
    for i in range(n):
        missing[i] = 1
 
    for i in range(1, n):
 
        # Inserting unfilled positions
        if (arr[i] == 0):
            unfilled_indices[i] = 1
             
        # Removing allocated_elements
        else:
            del missing[arr[i]]
 
    it2 = list(missing.keys())
    m = len(it2)
 
    # Loop for filling the positions
    # with arr[i] != i
    for it in unfilled_indices:
        arr[it] = it2[m - 1]
        m -= 1
 
    pos = 0
 
    # Checking for any arr[i] = i
    for i in range(1, n):
        if (arr[i] == i):
            pos = i
 
    x  = 0
 
    # Finding the suitable position
    # in the array to swap with found i
    # for which arr[i] = i
    if (pos != 0):
        for i in range(1, n):
            if (pos != i):
                 
                # Checking if the position
                # is present in unfilled_position
                if i in unfilled_indices:
                     
                    # Swapping arr[i] & arr[pos]
                    # (arr[pos] = pos)
                    x = arr[i]
                    arr[i] = pos
                    arr[pos] = x
                    break
 
    printArray(arr, n)
 
# Function to Print the array
def printArray(arr, n):
     
    for i in range(1, n):
        print(arr[i], end = " ")
 
# Driver Code
if __name__ == '__main__':
     
    arr = [ 0, 7, 4, 0, 3, 0, 5, 1 ]
 
    n = len(arr)
 
    solve(arr, n)
 
# This code is contributed by mohit kumar 29

C#

// C# implementation of above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
// Function to fill the position
// with arr[i] = 0
static void solve(int[] arr, int n)
{
    HashSet<int> unfilled_indices = new HashSet<int>();
    HashSet<int> missing = new HashSet<int>();
     
    // Inserting all elements in
    // missing[] set from 1 to N
    for(int i = 1; i < n; i++)
    {
        missing.Add(i);
    }
    for(int i = 1; i < n; i++)
    {
         
        // Inserting unfilled positions
        if (arr[i] == 0)
        {
            unfilled_indices.Add(i);
        }
         
        // Removing allocated_elements
        else
        {
            missing.Remove(arr[i]);
        }
    }
     
    int[] mi = new int[missing.Count];
    int l = 0;
     
    foreach(int x in missing)
    {
        mi[l++] = x;
    }
     
    int m = missing.Count;
     
    // Loop for filling the positions
    // with arr[i] != i
    foreach(int it in unfilled_indices)
    {
        arr[it] = mi[m - 1];
        m--;
    }
    int pos = 0;
     
    // Checking for any arr[i] = i
    for(int i = 1; i < n; i++)
    {
        if (arr[i] == i)
        {
            pos = i;
        }
    }
     
    // Finding the suitable position
    // in the array to swap with found i
    // for which arr[i] = i
    if (pos != 0)
    {
        for(int i = 1; i < n; i++)
        {
            if (pos != i)
            {
                 
                // Checking if the position
                // is present in unfilled_position
                if (unfilled_indices.Contains(i))
                {
                     
                    // Swapping arr[i] & arr[pos]
                    // (arr[pos] = pos)
                    int x = arr[i];
                    arr[i] = pos;
                    arr[pos] = x;
                    break;
                }
            }
        }
    }
    printArray(arr, n);
}
 
// Function to Print the array
static void printArray(int[] arr, int n)
{
    for(int i = 1; i < n; i++)
    {
        Console.Write(arr[i] + " ");
    }
}
 
// Driver Code
static public void Main()
{
    int[] arr = { 0, 7, 4, 0, 3, 0, 5, 1 };
    int n = arr.Length;
     
    solve(arr, n);
}
}
 
// This code is contributed by rag2127

Javascript

<script>
// Javascript implementation of above approach
 
 // Function to fill the position
  // with arr[i] = 0
function solve(arr,n)
{
    let unfilled_indices = new Set();
    let missing = new Set();
  
    // Inserting all elements in
    // missing[] set from 1 to N
    for (let i = 1; i < n; i++)
    {
      missing.add(i);
    }
    for (let i = 1; i < n; i++)
    {
  
      // Inserting unfilled positions
      if (arr[i] == 0)
      {
        unfilled_indices.add(i);
      }
  
      // Removing allocated_elements
      else
      {
        missing.delete(arr[i]);
      }
    }
    let mi = new Array(missing.size);
    let l = 0;
    for(let x of missing.values())
    {
      mi[l++] = x;
    }
    let m = missing.size;
  
    // Loop for filling the positions
    // with arr[i] != i
    for(let it of unfilled_indices.values())
    {
      arr[it] = mi[m - 1];
      m--;
    }
    let pos = 0;
  
    // Checking for any arr[i] = i
    for (let i = 1; i < n; i++)
    {
      if (arr[i] == i)
      {
        pos = i;
      }
    }
    let x;
  
    // Finding the suitable position
    // in the array to swap with found i
    // for which arr[i] = i
    if (pos != 0)
    {
      for (let i = 1; i < n; i++)
      {
        if (pos != i)
        {
  
          // Checking if the position
          // is present in unfilled_position
          if(unfilled_indices.has(i))
          {
  
            // Swapping arr[i] & arr[pos]
            // (arr[pos] = pos)
            x = arr[i];
            arr[i] = pos;
            arr[pos] = x;
            break;
          }
        }
      }
    }
    printArray(arr, n);
}
 
 // Function to Print the array
function printArray(arr,n)
{
    for (let i = 1; i < n; i++)
    {
      document.write(arr[i] + " ");   
    }
}
 
// Driver Code
let arr=[0, 7, 4, 0,3, 0, 5, 1 ];
let n = arr.length;
solve(arr, n);
         
// This code is contributed by unknown2108
</script>

Output:

7 4 6 3 2 5 1

Time Complexity: O(n)

Auxiliary Space: O(n)

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!