How To Honor Multiple Missing Integers Inward Given Array Of Numbers Amongst Duplicates Inward Java?

It's been a long fourth dimension since I convey discussed any coding or algorithm interview questions, therefore I idea to revisit i of the most pop array based coding employment of finding missing numbers inwards a given array of integers. You mightiness convey heard or seen this employment before on your programming chore interviews in addition to you lot mightiness already know how to solve this problem. But, at that topographic point are a lot of dissimilar versions of this employment amongst increasing difficulty levels which interviewers ordinarily purpose to confuse candidate in addition to farther examine their powerfulness to accommodate to frequent changes. In the yesteryear I convey demonstrated how to uncovering the missing expose inwards a sorted array as good on the unsorted integer array inwards Java using BitSet (see here), but, amongst simply i missing expose in addition to without whatever duplicates, which kinda brand those problems a fleck easier.

That makes the employment somewhat slow but what practice you lot practice if interviewer tells you lot that array contains duplicates and more than i numbers are missing? Well, that's what we'll utter over inwards this article, but before that let's acquire the employment arguing correctly.

1. Problem Statement

You convey given an integer array of size N. Array contains numbers from 1 to N-1 but a couplet of numbers are missing inwards an array which likewise contains duplicates.

Write a Java computer programme to impress the missing expose from the sequence.

For example, if given array is {1, 1, 2, 3, 5, 5, 7, 9, 9, 9} then it has length 10 and contains a expose from 1 to 9. In this case, missing numbers are 4, 6, in addition to 8.

2. Solution

When you lot run into the inquiry is to find missing expose inwards array, you lot mightiness yell back almost our before solution of calculating the amount of all the numbers and deducting it from expected amount to uncovering the missing number, but unfortunately that volition non operate inwards this province of affairs because more than i expose is missing as good it contains duplicates.

In this case, nosotros take to purpose a dissimilar approach, something similar a roll-call you lot would convey seen inwards your school.

The instructor has a register amongst names of all students, he goes through the listing in addition to grade absences on red. We tin purpose the same approach to uncovering all the missing numbers inwards the list.

We tin purpose an array every bit register in addition to it's an index every bit names of the numbers. You take to loop through the given array and tick marker all the numbers which are acquaint yesteryear storing i of their respective indices. For example, if the get-go expose inwards the given array is five (since the array is non sorted) therefore nosotros shop 1 on index five e.g. register[5] = 1

Once nosotros convey gone through all the numbers is given, nosotros tin become through our register array in addition to impress all the indices where the value is zero. These are absentees or missing numbers.

This solution is likewise prophylactic from duplicates because if a expose comes i time or twice nosotros simply shop 1 on the respective index.

Btw, if you lot are non familiar amongst array in addition to essential information construction e.g. linked list, binary tree, in addition to hash table, I propose you lot to get-go become through Data Structures in addition to Algorithms: Deep Dive Using Java to create a foundation.

3. Code

Now that nosotros know how to solve this employment of missing numbers in unsorted integer array with duplicates, it's fourth dimension to plow this solution into the code in addition to working Java program.

/*  * Java Program to find missing numbers inwards an integer  * array amongst duplicates. Array may contains to a greater extent than  * than i duplicates.  *   * input: {1, 1, 2, 3, 5, 5, 7, 9, 9, 9};  * output: 4, 6, 8  */ public class Hello {    public static void main(String[] args) {      // given input     int[] input = { 1, 1, 2, 3, 5, 5, 7, 9, 9, 9 };      // let's create about other array amongst same length     // yesteryear default all index volition comprise zero     // default value for int variable      int[] register = new int[input.length];      // right away let's iterate over given array to     // grade all acquaint numbers inwards our register     // array      for (int i : input) {       register[i] = 1;     }      // now, let's impress all the absentees     System.out.println("missing numbers inwards given array");      for (int i = 1; i < register.length; i++) {       if (register[i] == 0) {         System.out.println(i);       }     }   }  }

Output missing numbers in given array 4 6 8 

This is the simplest Java computer programme to solve this problem. You tin run into that we convey hardcoded the input array but you lot tin likewise modify the computer programme to acquire input from the user yesteryear using Scanner flat every bit shown inwards this example.

The code is just same every bit a solution, nosotros created about other array yesteryear copying length from master copy array in addition to used it grade numbers which are present.

Since array indices are likewise integer in addition to they are inwards the arrive at of input values nosotros tin leverage them to purpose both every bit information in addition to metadata. Had the array contains a number which is non inwards the arrive at of 1 to N-1 then nosotros couldn't convey used an array. If you lot desire to know to a greater extent than almost array information structure, you lot tin likewise see OutOfMemoryError inwards Java. This is fifty-fifty to a greater extent than possible because array needs a contiguous chunk of memory.

So, if nosotros tin take the additional array which is non actually belongings anything in addition to uncovering a way to simply shop missing expose which is quite less than the all the expose that nosotros tin amend this solution, something for you lot guys to think.

For time complexity, you lot tin run into that nosotros iterate through the whole array to grade all acquaint expose in addition to therefore iterate i time to a greater extent than to about other array of the same length to uncovering absentees. This way fourth dimension complexity of this solution is O(n) + O(n) or O(2N) which is inwards Big O Notation still O(n).

We tin farther amend this solution if we find a way to impress absentees every bit nosotros iterate through the given array. Again, something to yell back of you lot guys.

That's all almost this classic problem of finding missing numbers inwards a given integer array. In this part, nosotros convey constitute a solution for finding multiple missing numbers inwards the unsorted array amongst duplicates. The fourth dimension in addition to infinite complexity of our solution is O(n).


Further Learning
Data Structures in addition to Algorithms: Deep Dive Using Java
solution)

Find duplicate characters inwards a String? (solution)

50+ Data Structure in addition to Algorithms Interview Questions (list)

Check if String is Palindrome? (solution)

Find the highest occurred grapheme inwards a String? (solution)

Check if a String contains exclusively digits?  (solution)

10 Data Structure in addition to Algorithms courses for Interviews (courses)

Reverse String inwards Java using Iteration in addition to Recursion? (solution)

Count the expose of vowels in addition to consonants inwards a String? (solution)

Find the get-go non-repeated grapheme from String? (solution)

Count the occurrence of a given grapheme inwards String? (solution)

My favorite complimentary course of education to larn Data Structure in addition to Algorithms (courses)

Convert numeric String to an int? (solution)

Reverse words inwards a judgement without using a library method? (solution)

Reverse a String inwards house inwards Java? (solution)

Thanks for reading this article therefore far. If you lot similar this coding or algorithm interview inquiry in addition to my explanation therefore delight percentage amongst your friends in addition to colleagues. If you lot convey whatever incertitude or feedback therefore delight drib a note.

P.S. - If you lot are preparing for Programming Job Interview in addition to you lot take to a greater extent than such questions, tin depository fiscal establishment stand upwardly for the Data Structures in addition to Algorithms Bootcamp yesteryear Jonathan Rasmusson course of education on  Udemy.

Share this post