mjhjmtu

I have an array which carry some integer numbers. Say,numbers=3,0,1 or say, numbers=9,6,4,2,3,5,7,0,1. Now I have to find out the missing numbers from the array. As per this example there is only one missing number in each set. 1st one miss 2 and the 2nd one miss 8.

I have already code it. My code not only find out one missing number from specified set it can also find out more than 1 missing numbers from a given set.

But if two consecutive numbers are missing from same set it fail to find out.

My code
import java.util.Arrays;

public class Missing_number 

 public static void main( String args )
 
 int numbers=9,6,4,5,7,0,1;
 Arrays.sort(numbers);
 int i=1;

 while ( i < numbers.length ) 
 
 if ( numbers[i] - numbers[i-1] == 1 ) 
 
 
 else 
 
 System.out.println( "Missing number is " + ( numbers[i-1] + 1 ) );
 
 i++;
 
 

I am thinking like that if I am able to append the 1st missing number in the array and then start searching then how's the code look like? numbers=9,6,4,5,7,0,1 Now, 8 is already missing from this set. Now I have terminated two more element (2,3) from the list. Output: as per my code: 2,8 But 3 is also missing but that does not display.

I am thinking like if I am able to append 2 in number array then it may be little bit easier. But as we all know Java array is immutable so we cannot increase it's length.

So, maybe I will use List. But in list this type of indexing number[0]=somethingnot supported. So how could I proceed then. Am I using list or still stuck into array?

So I take a attempt to create it with an arraylist.

Mycode(modified version from array)

 public class T1 
 public static void main(String args)
 List<Integer> numbers=new ArrayList<>();
 numbers.add(9);
 numbers.add(6);
 numbers.add(4);
 numbers.add(5);
 numbers.add(7);
 numbers.add(0);
 numbers.add(1);
 Collections.sort(numbers);
 int i=1;
 while(i< numbers.size()) 
 if (numbers.get(i) - numbers.get(i-1) == 1) 

 else 
 System.out.println("Missing number is " + (numbers.get(i-1) + 1));
 numbers.add((numbers.get(i-1)+1));
 Collections.sort(numbers);
 
 i++;
 

 

Arraylist can solve my problem. But is there any possibility that a simple array can solve this problem?

This code uses a HashSet:

public static void main(String args) 
 int numbers = 9, 6, 4, 5, 7, 0, 1;
 Arrays.sort(numbers);
 HashSet<Integer> set = new HashSet<>();

 for (int i = numbers[0]; i < numbers[numbers.length - 1]; i++) 
 set.add(i);
 

 for (int i = 0; i < numbers.length; i++) 
 set.remove(numbers[i]);
 

 for (int x : set) 
 System.out.print(x + " ");
 

will print:

2 3 8 

Here is how it works:

1. Adds all numbers from the minimum number of the array to the maximum number of the array to the set.

2. Iterates through the array and removes every item of the array from the set.

3. Prints the remaining items in the set, which are all the missing items of the array.

replace the else clause to be:

for(int j=numbers[i-1] + 1; j <= numbers[i] - 1; j++) 
 System.out.println( "Missing number is " + ( j ) );

let's examine the case: 9 ,6 ,4 ,5 ,7 ,0 , 1
after sorting it will be: 0, 1, 4, 5, 6, 7, 9
now if i is at index 2 it finds the difference between numbers[i] and numbers[i-1] to be not equal 1 (4 - 1 = 3), now you need ALL the numbers between 1 and 4 which are 2, 3 and thus you must loop from numbers[i-1] to numbers[i] (exclusive) in order to achieve this.

The complexity of this code is big O of N (O(N)), where N is the biggest element in your array.

There are a lot of questions which are unanswered here. For Example, Does an array always start with zero?, What is the maximum possible size? etc.

Here is a simple way to approach this problem,

• Find the maximum number in your set.


• Create an empty boolean array of the length as that of the max number you found in the last step plus one.


• Scan your original set and set the value of your new boolean array at the index equal to the number in your original set as true.


• Finally scan your boolean array to find and pront all the indices with value false.

Example:

Original Set: 1,0,3

• 
  Step 1: Maximum number in the set = 3
  


• 
  Step 2: Boolean Array with Length = 3+1 --> false, false, false, false


• 
  Step 3: While scanning original set and setting values in the boolean array this will be the final state --> true, true, false, true


• 
  Step 4: You'll finally scan the boolean array to print 2 since this it is only index which has value = false
  

int numbers = 11, 6, 4, 5, 7, 1 ;
Arrays.sort(numbers);
int numbersArrayIndex = 0;
for (int i = 0; i < numbers[numbers.length - 1]; i++) 
 if (i == numbers[numbersArrayIndex]) 
 numbersArrayIndex++;
 
 else 
 System.out.println(i);