Missing number in array java

How to Find Multiple Missing Integers in Given Array of Numbers with Duplicates in Java?

Hello guys, It’s been a long time since I have discussed any coding or algorithm interview questions, so I thought to revisit one of the most popular array-based coding problems of finding missing numbers in a given array of integers. You might have heard or seen this problem before on your programming job interviews and you might already know how to solve this problem. But, there are a lot of different versions of this problem with increasing difficulty levels which interviewers normally use to confuse candidates and further test their ability to adapt to frequent changes, which is key to surviving in the ever-changing software development world.

In the past I have demonstrated how to find the missing number in a sorted array as well on the unsorted integer array in Java using BitSet (see here), but, with just one missing number and without any duplicates, which kind of make those problems a bit easier.

That makes the problem somewhat easy but what do you do if the interviewer tells you that array contains duplicates and more than one numbers are missing? Well, that’s what we’ll discuss in this article, but before that let’s get the problem statement correctly.

Btw, it’s also helpful to know the essential coding patterns like Sliding Window, Two Pointers, Fast and Slow Pointers, Merge Intervals, Cyclic Sort, and Top K elements that can help you to solve many frequently asked coding problems.

Many programmers miss that part and instead went to prepare for 100+ Leetcode problems which often require more time and still they struggle to solve a new coding problem which they have never seen before.

To avoid this mistake I suggest you go through Grokking the Coding Interview: Patterns for Coding Questions an interactive and useful course on Educative and learn those essential 15+ coding patterns for interviews.

1. Problem — How to Find more than missing numbers in Array with Duplicates?

You have given an integer array of size N. Array contains numbers from 1 to N-1 but a couple of numbers are missing in an array which also contains duplicates.

Write a Java program to print the missing number from the sequence.

For example, if the given array is then it has length 10 and contains a number from 1 to 9. In this case, missing numbers are 4, 6, and 8.

2. The solution to finding missing numbers from the given array

When you see the question is to find the missing number in an array, you might think about our earlier solution of calculating the sum of all the numbers and deducting it from the expected sum to find the missing number, but unfortunately, that will not work in this situation because more than one number is missing as well it contains duplicates.

In this case, we need to use a different approach, something like a roll-call you would have seen in your school.

The teacher has a register with the names of all students, he goes through the list and marks absences on red. We can use the same approach to find all the missing numbers in the list.

We can use an array as register and it’s an index as names of the numbers. You need to loop through the given array and tick marking all the numbers which are present by storing one of their respective indices. For example, if the first number in the given array is 5 (since the array is not sorted) then we store 1 on index 5 e.g. register[5] = 1

Once we have gone through all the numbers is given, we can go through our register array and print all the indices where the value is zero. These are absentees or missing numbers.

This solution is also safe from duplicates because if a number comes once or twice we just store 1 on the respective index.

Btw, if you are not familiar with array and essential data structure like a linked list, binary tree, and hash table, I suggest you first go through Data Structures and Algorithms: Deep Dive Using Java to build a foundation.

3. Code

Now that we know how to solve this problem of missing numbers in unsorted integer array with duplicates, it’s time to turn this solution into the code and working Java program.

/* * Java Program to find missing numbers in an integer * array with duplicates. Array may contains more * than one duplicates. * * input: ; * 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 another array with same length // by default all index will contain zero // default value for int variable int[] register = new int[input.length]; // now let's iterate over given array to // mark all present numbers in our register // array for (int i : input) < register[i] = 1; > // now, let's print all the absentees System.out.println("missing numbers in 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 program to solve this problem. You can see that we have hardcoded the input array but you can also modify the program to get input from the user by using Scanner class as shown in this example.

The code is exactly the same as a solution, we created another array by copying length from the original array and used it mark numbers that are present.

Since array indices are also an integer and they are in the range of input values we can leverage them to use both as data and metadata. Had the array contains a number which is not in the range of 1 to N-1 then we couldn’t have used an array. If you want to know more about the array data structure, you can also see Algorithms and Data Structures — Part 1 and 2 courses on Pluralsight.

Here is the summary of the algorithm and code in a slide for better understanding:

4. Analysis and Explanation of Logic

Now, the time is to analyze our solution to find the CPU and Memory complexity using Big O notation. If you look at the code then you will find that we are creating another array with the same size which means it has memory or space complexity of O(n).

This means if the array is too big like contains all the numbers in the integer range then we would a lot more memory which may not be available and our program could throw OutOfMemoryError in Java. This is even more possible because array needs a contiguous chunk of memory.

So, if we can remove the additional array which is not really holding anything and find a way to just store missing numbers which is quite less than all the numbers that we can improve this solution, something for you guys to think.

For time complexity, you can see that we iterate through the whole array to mark all present numbers and then iterate again to another array of the same length to find absentees. This means the time complexity of this solution is O(n) + O(n) or O(2N) which is in Big O Notation still O(n).

We can further improve this solution if we find a way to print absentees as we iterate through the given array. Again, something to think of you guys.

That’s all about this classic problem of finding missing numbers in a given integer array. In this part, we have found a solution for finding multiple missing numbers in the unsorted array with duplicates. The time and space complexity of our solution is O(n).

• Print duplicate characters from String? (solution)
• Find duplicate characters in a String? (solution)
• 50+ Data Structure and Algorithms Interview Questions (list)
• Check if String is Palindrome? (solution)
• 20+ array-based coding problems from interviews (questions)
• 10 free Data Structure Courses for Beginners (Free DSA courses)
• Find the highest occurred character in a String? (solution)
• Check if a String contains only digits? (solution)
• Reverse String in Java using Iteration and Recursion? (solution)
• Count the number of vowels and consonants in a String? (solution)
• Find the first non-repeated character from String? (solution)
• Count the occurrence of a given character in String? (solution)
• My favorite free course to learn Data Structure and Algorithms (courses)
• Convert numeric string to an int? (solution)
• Reverse words in a sentence without using a library method? (solution)
• Reverse a String in place in Java? (solution)

P.S. — If you are preparing for Programming Job Interview and you need more such questions, you can check the Data Structures and Algorithms Bootcamp by Jonathan Rasmusson course on Udemy. This is a great course to build and level up your Data Structure and Algorithms skills to become a better programmer.

Источник

Java program to find missing number in an array

If you want to practice data structure and algorithm programs, you can go through data structure and algorithm interview questions.

Problem :

You are given an integer array containing 1 to n but one of the number from 1 to n in the array is missing. You need to provide optimum solution to find the missing number. Number can not be repeated in the arry.
For example:

Solution:

1. Find the sum of n number using formula n=n*(n+1)/2
2. Find the sum of elements present in given array.
3. Substract (sum of n numbers – sum of elements present in the array).

Java program to find missing number in an array:

When you run above program, you will get below output:

Was this post helpful?

You may also like:

Search for a range Leetcode – Find first and last position of element in sorted array

Sort an array of 0s, 1s and 2s

Check if it is possible to reach end of given Array by Jumping

Check if Array Elements are Consecutive

Find the local minima in array

Sliding Window Maximum in java

Count number of occurrences (or frequency) of each element in a sorted array

Find subarrays with given sum in an array.

Count 1’s in sorted Binary Array

Find peak element in the array

You may also like:

[Fixed] Unable to obtain LocalDateTime from TemporalAccessor

Convert LocalDate to Instant in Java

Convert Instant to LocalDate in Java

Convert String to LocalDateTime in Java

Format LocalDateTime to String in Java

Java 8 – Find duplicate elements in Stream

How to format Instant to String in java

Java Date to LocalDate

Java LocalDate to Date

Java Stream to List

Share this

Related Posts

Author

Related Posts

Search for a range Leetcode – Find first and last position of element in sorted array

Table of ContentsApproach 1 (Using Linear Search)Approach 2 (Using Modified Binary Search-Optimal) In this article, we will look into an interesting problem asked in Coding Interviews related to Searching Algorithms. The problem is: Given a Sorted Array, we need to find the first and last position of an element in Sorted array. This problem is […]

Sort an array of 0s, 1s and 2s

Table of ContentsProblemSolution If you want to practice data structure and algorithm programs, you can go through Java coding interview questions. In this post, we will see how to sort an array of 0s, 1s and 2s.We have already seen a post on sort 0s and 1s in an array. Problem Given an array containing zeroes, […]

Check if it is possible to reach end of given Array by Jumping

Table of ContentsProblemSolution If you want to practice data structure and algorithm programs, you can go through Java coding interview questions.   Problem Given an array with positive integers as elements indicating the maximum length of a jump which can be made from any position in the array. Check if it is possible to have […]

Check if Array Elements are Consecutive

Table of ContentsProblemSolutionProgram to check if Array Elements are Consecutive If you want to practice data structure and algorithm programs, you can go through 100+ data structure and algorithm programs. In this post, we will see how to check if array elements are consecutive. Problem Given an array, we need to check if array contains […]

Find the local minima in array

Table of ContentsProblemSolutionNaive approachEfficient approach If you want to practice data structure and algorithm programs, you can go through Java coding interview questions. In this post, we will see how to find the local minima in the array. Problem An element is local minima if it is less than its neighbors. int [] arr =

Sliding Window Maximum in java

Table of ContentsProblemSolution If you want to practice data structure and algorithm programs, you can go through Java coding interview questions. In this post, we will see about Sliding Window Maximum in java Problem Given an Array of integers and an Integer k, Find the maximum element of from all the contiguous subarrays of size K. […]

Источник