Given an array of unique integers where each integer of the given array lies in the range [1, N]. The size of array is (N-4). No Single element is repeated. Hence four numbers from 1 to N are missing in the array. Find the 4 missing numbers in sorted order.
Examples:
Input : arr[] = {2, 5, 6, 3, 9}
Output : 1 4 7 8
Input : arr[] = {1, 7, 3, 13, 5, 10, 8, 4, 9}
Output : 2 6 11 12
A simple O(N) solution is to use an auxiliary array of size N to mark visited elements. Traverse the input array and mark elements in the auxiliary array. Finally print all those indexes that are not marked.
How to solve with O(1) auxiliary space?
We initialize an array named helper of length 4 in order to compensate the 4 missing numbers and fill them with zero. Then we iterate from i=0 to i < length_of_array of the given array and take the Absolute of the i-th element and store it in a variable named temp.
Now we will check:
- If the element’s absolute value is less than the length of the input array then we will multiply the array[temp] element with -1 (in order to mark the visited element).
- If the element’s absolute value is greater than the length of the input array then we will put the value of helper[temp%array.length] element with -1 (in order to mark the visited element).
Then we iterate over input array and those index whose value is still greater than zero then those elements were not encountered in the input array. So we print the (index+1) value of the index whose element is greater than zero.
Then we will iterate over helper array and those index whose value is still greater than zero then those elements were not encountered in the input array. So we print the (index+array.length+1) value of the index whose element is greater than zero.
Implementation:
C++
// CPP program to find missing 4 elements// in an array of size N where elements are// in range from 1 to N+4.#include <bits/stdc++.h>using namespace std;// Finds missing 4 numbers in O(N) time// and O(1) auxiliary space.void missing4(int arr[], int n){ // To keep track of 4 possible numbers // greater than length of input array // In Java, helper is automatically // initialized as 0. int helper[4]; // Traverse the input array and mark // visited elements either by marking // them as negative in arr[] or in // helper[]. for (int i = 0; i < n; i++) { int temp = abs(arr[i]); // If element is smaller than or // equal to length, mark its // presence in arr[] if (temp <= n) arr[temp - 1] *= (-1); // Mark presence in helper[] else if (temp > n) { if (temp % n != 0) helper[temp % n - 1] = -1; else helper[(temp % n) + n - 1] = -1; } } // Print all those elements whose presence // is not marked. for (int i = 0; i < n; i++) if (arr[i] > 0) cout << (i + 1) << " "; for (int i = 0; i < 4; i++) if (helper[i] >= 0) cout << (n + i + 1) << " "; return;}// Driver codeint main(){ int arr[] = { 1, 7, 3, 12, 5, 10, 8, 4, 9 }; int n = sizeof(arr) / sizeof(arr[0]); missing4(arr, n); return 0;}// This code is contributed by Nikita Tiwari. |
Java
// Java program to find missing 4 elements// in an array of size N where elements are// in range from 1 to N+4.class Missing4 { // Finds missing 4 numbers in O(N) time // and O(1) auxiliary space. public static void missing4(int[] arr) { // To keep track of 4 possible numbers // greater than length of input array // In Java, helper is automatically // initialized as 0. int[] helper = new int[4]; // Traverse the input array and mark // visited elements either by marking // them as negative in arr[] or in // helper[]. for (int i = 0; i < arr.length; i++) { int temp = Math.abs(arr[i]); // If element is smaller than or // equal to length, mark its // presence in arr[] if (temp <= arr.length) arr[temp - 1] *= (-1); // Mark presence in helper[] else if (temp > arr.length) { if (temp % arr.length != 0) helper[temp % arr.length - 1] = -1; else helper[(temp % arr.length) + arr.length - 1] = -1; } } // Print all those elements whose presence // is not marked. for (int i = 0; i < arr.length; i++) if (arr[i] > 0) System.out.print(i + 1 + " "); for (int i = 0; i < helper.length; i++) if (helper[i] >= 0) System.out.print(arr.length + i + 1 + " "); return; } // Driver code public static void main(String[] args) { int[] arr = { 1, 7, 3, 12, 5, 10, 8, 4, 9 }; missing4(arr); }} |
Python3
# Python 3 program to find missing 4 elements# in an array of size N where elements are# in range from 1 to N+4.# Finds missing 4 numbers in O(N) time # and O(1) auxiliary space.def missing4( arr) : # To keep track of 4 possible numbers # greater than length of input array # In Java, helper is automatically # initialized as 0. helper = [0]*4 # Traverse the input array and mark # visited elements either by marking # them as negative in arr[] or in # helper[]. for i in range(0,len(arr)) : temp = abs(arr[i]) # If element is smaller than or # equal to length, mark its # presence in arr[] if (temp <= len(arr)) : arr[temp - 1] = arr[temp - 1] * (-1) # Mark presence in helper[] elif (temp > len(arr)) : if (temp % len(arr)) : helper[temp % len(arr) - 1] = -1 else : helper[(temp % len(arr)) +len(arr) - 1] = -1 # Print all those elements whose presence # is not marked. for i in range(0, len(arr) ) : if (arr[i] > 0) : print((i + 1) , end=" ") for i in range(0, len(helper)) : if (helper[i] >= 0) : print((len(arr) + i + 1) , end=" ") # Driver codearr = [ 1, 7, 3, 12, 5, 10, 8, 4, 9 ]missing4(arr)# This code is contributed# by Nikita Tiwari. |
C#
// C# program to find missing 4 elements// in an array of size N where elements are// in range from 1 to N+4.using System;class Missing4 { // Finds missing 4 numbers in O(N) time // and O(1) auxiliary space. public static void missing4(int[] arr) { // To keep track of 4 possible numbers // greater than length of input array // In Java, helper is automatically // initialized as 0. int[] helper = new int[4]; // Traverse the input array and mark // visited elements either by marking // them as negative in arr[] or in // helper[]. for (int i = 0; i < arr.Length; i++) { int temp = Math.Abs(arr[i]); // If element is smaller than or // equal to length, mark its // presence in arr[] if (temp <= arr.Length) arr[temp - 1] *= (-1); // Mark presence in helper[] else if (temp > arr.Length) { if (temp % arr.Length != 0) helper[temp % arr.Length - 1] = -1; else helper[(temp % arr.Length) + arr.Length - 1] = -1; } } // Print all those elements whose presence // is not marked. for (int i = 0; i < arr.Length; i++) if (arr[i] > 0) Console.Write(i + 1 + " "); for (int i = 0; i < helper.Length; i++) if (helper[i] >= 0) Console.Write(arr.Length + i + 1 + " "); return; } // Driver code public static void Main() { int[] arr = { 1, 7, 3, 12, 5, 10, 8, 4, 9 }; missing4(arr); }}//This code is contributed by Anant Agarwal. |
PHP
<?php// PHP program to find missing 4 elements// in an array of size N where elements // are in range from 1 to N+4.// Finds missing 4 numbers in O(N) time// and O(1) auxiliary space.function missing4($arr, $n){ // To keep track of 4 possible numbers // greater than length of input array // initialized as 0. $helper = array(0, 0, 0, 0); // Traverse the input array and mark // visited elements either by marking // them as negative in arr[] or in // helper[]. for ($i = 0; $i < $n; $i++) { $temp = abs($arr[$i]); // If element is smaller than or // equal to length, mark its // presence in arr[] if ($temp <= $n) $arr[$temp - 1] = $arr[$temp - 1] * (-1); // Mark presence in helper[] else if ($temp > $n) { if ($temp % $n != 0) $helper[$temp % $n - 1] = -1; else $helper[($temp % $n) + $n - 1] = -1; } } // Print all those elements whose // presence is not marked. for ($i = 0; $i < $n; $i++) if ($arr[$i] > 0) { $a = $i + 1; echo "$a", " "; } for ($i = 0; $i < 4; $i++) if ($helper[$i] >= 0) { $b = $n + $i + 1; echo "$b", " "; } echo "\n"; return;}// Driver code$arr = array(1, 7, 3, 12, 5, 10, 8, 4, 9);$n = sizeof($arr);missing4($arr, $n);// This code is contributed by iAyushRaj?> |
Javascript
<script>// Javascript program to find missing 4 elements// in an array of size N where elements are// in range from 1 to N+4.// Finds missing 4 numbers in O(N) time // and O(1) auxiliary space.function missing4(arr) { // To keep track of 4 possible numbers // greater than length of input array // In Java, helper is automatically // initialized as 0. let helper =[]; for(let i = 0; i < 4; i++) { helper[i] = 0; } // Traverse the input array and mark // visited elements either by marking // them as negative in arr[] or in // helper[]. for(let i = 0; i < arr.length; i++) { let temp = Math.abs(arr[i]); // If element is smaller than or // equal to length, mark its // presence in arr[] if (temp <= arr.length) arr[temp - 1] = Math.floor(arr[temp - 1] * (-1)); // Mark presence in helper[] else if (temp > arr.length) { if (temp % arr.length != 0) helper[temp % arr.length - 1] = -1; else helper[(temp % arr.length) + arr.length - 1] = -1; } } // Print all those elements whose presence // is not marked. for(let i = 0; i < arr.length; i++) if (arr[i] > 0) document.write(i + 1 + " "); for(let i = 0; i < helper.length; i++) if (helper[i] >= 0) document.write(arr.length + i + 1 + " "); return;}// Driver codelet arr = [ 1, 7, 3, 12, 5, 10, 8, 4, 9 ];missing4(arr);// This code is contributed by susmitakundugoaldanga </script> |
Output
2 6 11 13
Time Complexity: O(N)
Auxiliary Space: O(1)
This article is contributed by Sanket Singh 2. If you like neveropen and would like to contribute, you can also write an article using contribute.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
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!
