Algorithm
1. First, we sort the given array using the sorting function.
2. After sorting, Now we start iterating the element: Ignore the negative element and as soon as we get a positive number, keep monitoring numbers.
3. Whenever we find numbers are mismatching, we add numbers to the missing list.
4. The process continues till the amount required to be printed is exhausted. We print the missing elements
Implementation
Now that we have an idea to solve this problem of missing numbers in an integer array. We will try to turn this solution into a code and get it working. Below we will see the implementation of the algorithm in different programming languages.
Java Code
/* Copy this code in a file named "ArrayApp.java" */
import java.util.List;
import java.util.Set;
import java.util.ArrayList;
import java.util.HashSet;
public class ArrayApp {
public static List<Integer>
/* Calling the function passing the argument array */
firstKMissingNaturalNumbers(int[] array, int k) {
/* Negative test case for making sure the number is natural */
if(array.length == 0 || k < 1) {
return new ArrayList<>();
}
int i = 0;
while(i < array.length) {
/* Iterating the number till the number is less than the length of the array*/
if(array[i] > 0 && array[i] <= array.length && array[i] != array[array[i] - 1]) {
int otherIndex = array[i] - 1;
/* Swap operation */
int x = array[i];
array[i] = array[otherIndex];
array[otherIndex] = x;
} else {
i++;
}
}
/* Here putting all the missing values */
List<Integer> missing = new ArrayList<Integer>();
/* Here putting all the other numbers */
Set<Integer> otherNumber = new HashSet<Integer>();
for(i = 0; i < array.length & missing.size() < k; i++) {
/* We will check if array of i is not equal to i+1 */
if(array[i] != i + 1) {
/* Ideally the missing value is i+1 */
missing.add(i + 1);
/* The value present here will add up to others number */
otherNumber.add(array[i]);
}
}
/* Iterating here that for j=i , missing size is less than k
adding more missing values */
for(int j = i; missing.size() < k; j++) {
/* If the value is not present in the other number , i.e. if the value is not there in the hashset, then it will be added in the missing values */
if(!otherNumber.contains(j + 1) ) {
missing.add(j + 1);
}
}
return missing;
}
public static void main(String[] args) {
/*declaring the array*/
int[] array = { -2, 3, 4, 5, 7};
/* Printing the array with the k numbers of missing elements to be printed */
System.out.print("The 'k' missing numbers are: ");
System.out.println(ArrayApp.firstKMissingNaturalNumbers(array, 2));
}
}
You can also try this code with Online Java Compiler
Output:
The 'k' missing numbers are: [1, 2]
Also see, Morris Traversal for Inorder.
Frequently Asked Questions
What is the most efficient way to search an unsorted array?
An array is a group of items stored at adjacent memory locations. Hence, sequential search, also known as linear search, is the best way to find an element in an array .
What is the time complexity of the problem?
The Time Complexity of the code above is O(n log (n)).
Can a negative number be passed as the size of an Array?
No, a negative integer cannot be passed at an array size. As the array size represents the number of elements in an array and it cannot be negative .
Also Read - Strong number in c
Conclusion
This article has presented a simple solution to the classic problem of finding missing numbers in the given integer array. We made sure that the missing K natural numbers not present were displayed. We also saw the algorithms and showed how they can be implemented .
Refer to our courses and practice questions on Coding Ninjas Studio. You can also check out more blogs on arrays to follow.
Do upvote our blog to help other ninjas grow. Happy Coding!
117+ registered 