0

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.

Community
  • 1
  • 1
Julia
  • 61
  • 2
  • 6

3 Answers3

3

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.

Maciej Sikora
  • 19,374
  • 4
  • 49
  • 50
  • Did you notice ***unsorted***? – PM 77-1 Aug 08 '16 at 19:19
  • Did you notice his first two words: "Sort array"? – GhostCat Aug 08 '16 at 19:19
  • @PM77-1, yes - hence "_sort array_". – Boris the Spider Aug 08 '16 at 19:19
  • Unsorted is not mean - cannot be sorted. – Maciej Sikora Aug 08 '16 at 19:20
  • Would this work if the two missing numbers are consecutive? And/Or if one of the missing numbers is 1? – jonhopkins Aug 08 '16 at 19:21
  • It will work well on every situation, to store missing numbers just create second array – Maciej Sikora Aug 08 '16 at 19:22
  • Who has ever upvoted this question? The solution is O(n) time and O(1) memory. – xenteros Aug 08 '16 at 19:22
  • 2
    @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. – jonhopkins Aug 08 '16 at 19:28
  • @jonhopkins it is not true if for example is missing 3,4,5 then on 3 - previous( is 2)+1!=6 so add 3 and set previous as 3 - next loop previous( is 3) + 1!=6 so add 4 and next next... – Maciej Sikora Aug 08 '16 at 19:31
  • That's the trick I was hoping would be mentioned in the answer. If you store `previous` as a separate variable and make sure to update it when you find a missing number and try the same loop iteration again, then yes this will work. The way the answer is currently worded sounds (in my opinion) more like "loop through the array and check if the last element is the current element - 1" – jonhopkins Aug 08 '16 at 19:36
  • @jonhopkins thanks, i edited answer and mentioned about this. – Maciej Sikora Aug 08 '16 at 19:42
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.

GhostCat
  • 137,827
  • 25
  • 176
  • 248
  • It would be better to use an `array` than a `List` but you still have my upvote. – nhouser9 Aug 08 '16 at 19:21
  • 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. – GhostCat Aug 08 '16 at 19:23
  • 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. – nhouser9 Aug 08 '16 at 19:26
  • @nhouser9 Who told you that? ArrayList index access has O(1) [ http://stackoverflow.com/questions/26638207/how-does-the-list-has-fast-random-access-in-java ] – GhostCat Aug 08 '16 at 19:28
  • 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: http://image.slidesharecdn.com/24-algorithms-complexity-and-data-structures-efficiency-120712075728-phpapp02/95/24-algorithms-complexity-and-data-structures-efficiency-c-fundamentals-27-728.jpg?cb=1342080060 – nhouser9 Aug 08 '16 at 19:32
  • I still dont get it. Indexing is O(1), not O(n). Yes adding elements is expensive at some point, but if you create the list with an initial capacity of 100, there is no difference to an array; except all the benefits that using collection things give you. – GhostCat Aug 08 '16 at 19:35
  • the point that you are missing is that `ArrayList` is actually an `array` not a `List`. – nhouser9 Aug 08 '16 at 20:31
1

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);
    }
}
Chris Gong
  • 8,031
  • 4
  • 30
  • 51
  • Wrong answer. The solution is O(N) time and O(1) mem. Look at marked duplicate topic. – xenteros Aug 08 '16 at 19:24
  • @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. – GhostCat Aug 08 '16 at 19:25
  • It's popular problem. If I ask you about sorting would you give me log(n^2) solution? – xenteros Aug 08 '16 at 19:27
  • @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. – Chris Gong Aug 08 '16 at 19:27
  • @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 – Bohemian Aug 08 '16 at 20:02
  • @boh it's interview question. If you don't in an optimal way you lose :) – xenteros Aug 08 '16 at 20:14