Find 2 missing numbers in an unsorted array 1 to 100. (Java) [duplicate]

Question

This question already has answers here:

Easy interview question got harder: given numbers 1..100, find the missing number(s) given exactly k are missing (48 answers)

Closed 9 years ago.

I am struggling with the logic behind solving the following prompt: An unsorted integer array contains 98 different numbers from 1 to 100. So, among the numbers from 1 to 100, two distinct numbers are missing. Find them.

I understand the concept behind finding one missing number, its the second one that's giving me issues. Any suggestions?

Yes, I have seen this entry, but I found the answers given to be either too complex and detailed or off topic. I am a java beginner - just trying to wrap my head around this.

Edit: This is where I am at following initiating an array with numbers 1-100 and then sorting them:

for (int i = 0; i < arr.length; i++) {
 int j = i + 1; 
 if (arr[j] - arr[i] > 1){
 int missing = arr[i + 1]; 
 System.out.println(missing);
 } 
 }

My issue now is that I cannot get the loop to print the actual missing number. It prints the number above the missing number. I have tried a few different ways and it always either prints the number above or below, never the actual missing number.

• Chris Gong: Can you post what you have tried so far so that we can try to find the source of confusion?
• PM 77-1: Use both Sum (Euler) and Product (Factorial) You will need BigInteger. That will give you O(N) time and O(1) storage.
• xenteros: Have you at least google it before posting?
• Julia: Wouldn't have posted if I hadn't.
• Bohemian: @pm77 precise product, ie n!, is at least O(n ^ 1.5)

Answer 1

Sort array and then do loop and if next element in loop is not previous+1 then it is missing one. Save previous value to separate variable for more distincts numbers one after another.

• PM 77-1: Did you notice unsorted?
• GhostCat: Did you notice his first two words: "Sort array"?
• Boris the Spider: @PM77-1, yes - hence "sort array".
• Maciej Sikora: Unsorted is not mean - cannot be sorted.
• jonhopkins: @MaciejSikora I asked because if you do a simple loop through the array with a simple check, then if you have, for example, 3 and 4 are missing, you get 1 and 2, then 5. 5 is not 2+1, so it would notice that 3 is missing. But if you simply continue the loop at the next element, which is 5, it will never find another missing number. And if 1 is missing, you would have to check for that before the loop or else it would be missed.

Answer 2

Create a 'List' with 100 entries; each value set to false on startup.

Iterate your array, and simply take each entry as index in that list of Booleans - and toggle the value there to true.

In the end, the boolean list contains two values with false; their indices making up the two missing numbers.

• nhouser9: It would be better to use an array than a List but you still have my upvote.
• GhostCat: Why is that? I mean; why do you prefer an array? Because the initial assignment has a fixed size? And thanks for the upvote; I was really puzzled why the other question got upvoted; and I got a downvote 2 seconds after posting my answer.
• nhouser9: I prefer an array because indexing into it takes constant time as opposed to time proportional to the length of the list, and there is no downside because the array / list will always be a fixed size.
• GhostCat: @nhouser9 Who told you that? ArrayList index access has O(1) [ stackoverflow.com/questions/26638207/… ]
• nhouser9: that's because ArrayList is implemented behind the scenes using an array that can dynamically grow. It is not a true list. As for "who told me that", I learned it in my six years at college. See this image for the time complexity of accessing elements in various data structures: image.slidesharecdn.com/…

Answer 3

Let's say your unsorted int array is called arr. Now make a boolean array with 100 elements in it, all initialized to false (default value). As you iterate through arr mark the corresponding element in the boolean array as true. For example, if the first element in arr is 20, then make visited[19] true. After doing this, iterate through the boolean array to see which two indices are false, and this will tell you which two numbers were missing. Here's what it should look like,

boolean visited = new boolean[100];
for(int i = 0; i < arr.length; i++){
 visited[arr[i] - 1] = true;
}
for(int i = 0; i < visited.length; i++){
 if(!visited[i]){
 System.out.println(i + 1);
 }
}

• xenteros: Wrong answer. The solution is O(N) time and O(1) mem. Look at marked duplicate topic.
• GhostCat: @xenteros The answer is not wrong. Maybe it is not optimal. But it gives the expected output. And this question itself did not put any constraints on time and memory Os.
• xenteros: It's popular problem. If I ask you about sorting would you give me log(n^2) solution?
• Chris Gong: @xenteros As GhostCast points out, the OP never explicitly stated that big O was a factor here. However, I do see your point, my answer is not the most efficient memory-wise.
• Bohemian: @xen importantly, it doesn't require a sort, and O(n) time is the fastest possible. The only down side is O(n) space complexity, but it could quickly handle even large number ranges