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 arrayvoid printArray(int[], int);// Function to fill the position// with arr[i] = 0void 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 arrayvoid printArray(int arr[], int n){ for (int i = 1; i < n; i++) cout << arr[i] << " ";}// Driver Codeint 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 approachimport 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] = 0def 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 arraydef printArray(arr, n): for i in range(1, n): print(arr[i], end = " ")# Driver Codeif __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 approachusing System;using System.Collections.Generic;class GFG{// Function to fill the position// with arr[i] = 0static 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 arraystatic void printArray(int[] arr, int n){ for(int i = 1; i < n; i++) { Console.Write(arr[i] + " "); }}// Driver Codestatic 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] = 0function 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 arrayfunction printArray(arr,n){ for (let i = 1; i < n; i++) { document.write(arr[i] + " "); }}// Driver Codelet 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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
