Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
3.
Algorithm
3.1.
Implementation 
3.1.1.
Java Code
4.
Frequently Asked Questions
4.1.
What is the most efficient way to search an unsorted array?
4.2.
What is the time complexity of the problem?
4.3.
Can a negative number be passed as the size of an Array?
5.
Conclusion
Last Updated: Mar 27, 2024
Easy

Find First K Natural Numbers Missing in the Given Array

Create a resume that lands you SDE interviews at MAANG
Speaker
Anubhav Sinha
SDE-2 @
12 Jun, 2024 @ 01:30 PM

Introduction

Here we will see one of the most popular array-based coding problems of finding the first K natural numbers in the given array. You might have heard or seen similar problems before in your programming tests. Still, there are a lot of different versions of increasing difficulty levels that the interviewer uses typically. They do it to confuse candidates and further test their ability to adapt to frequent changes. This problem is slightly different as we may have to find multiple integers missing in the array. 

So, in an array of size n and a number k, our goal is to print first k natural numbers that are not present in the given array.

Must Read, Array Implementation of Queue and  Rabin Karp Algorithm

Problem Statement

We take an integer array of size N. The Array has numbers from 1 to N-1, but a few numbers are missing in an array. Here we write a program in C++ to print the missing number from the sequence.

For example, if the array given is {1, 2, 3, 5, 8, 9}

Given that the array size is n and the number k=3, we need to print the first 3 natural numbers absent in the given array. In this case, the missing numbers are 4, 6, and 7.
 

Examples: 

Input : {1 2 3 4 8 9} 
         k = 3
Output : The missing numbers are: 5 6 7
Input  : {-2 -3 4 5 7}
          k = 2
Output : The missing numbers are: 1 2
Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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));
  }
}


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!

Previous article
Difference Between Linear Array And A Record
Next article
For Each Loop
Live masterclass