Hello! So I’m doing a 30 day coding challenge where I solve around 3-5 questions per day and thought of posting them here on my blog so that you guys can join the challenge too!
Welcome to Coding challenge Day 2: Problem one! Be sure to post your answers, queries etc in the comments!!
Problem: To find missing number in integer array from one to hundred
Sample input: array= {1,2,3,5,6,7};
Output: Missing number in array [1, 2, 3, 5, 6, 7] with total of 7 elements is 4
Sample input: array= {1,2,3,5,6,7,9};
Output: Missing number in array [1, 2, 3, 5, 6, 7] with total of 7 elements is 4 8
Sample input: array= {1,2,3,5,7,9};
Output: Missing number in array [1, 2, 3, 5, 7, 9] with total of 9 elements is 4 6 8
Solution:
- So I’ve solved this problem using BitSet, in case there are more than one element missing (if only one element is missing then you can find the sum of all the elements in the array and subtract from 100 to find the missing element)
- For simplicity’s sake I’ve taken a smaller array of integers, So start out by finding the number of missing elements
- Then traverse the integer array and set the numbers in the bit array according to (corresponding index-1)
- You can now find missing elements by finding which index numbers are empty
import java.util.Arrays;
import java.util.BitSet;
//find missing element from 1-100
public class Program001missing_element_in_array {
public static void main (String [] args){
int [] array= {1,2,3,5,7,9};
int original_array_size= 9;
Missing_element(array, original_array_size);
}
public static void Missing_element (int [] array, int size){
int missing_count= size- array.length;
BitSet bitset = new BitSet(size);
for (int number : array){
bitset.set(number-1);
}
System.out.printf("Missing number in array %s with total of %d elements is ", Arrays.toString(array), size );
int missingindex=0;
for(int i=0; i<missing_count; i++){
missingindex= bitset.nextClearBit(missingindex);
System.out.print(++missingindex +" ");
}
}
}
Happy Learning!!