Showing posts with label finding missing number in an array. Show all posts
Showing posts with label finding missing number in an array. Show all posts ## How to find missing number in a sequential array ?

Given a list of sequential integers and need to finding a missing number from the list of numbers. For example if we have an array like

Example:1
array = {1,2,3,5,6}
Finding missing number 4

Example:2
array = {14,15,16,18,19,20}
then the missing number is 17

Using XOR operation and finding the missing number.

• Iterate all the elements and do XOR with each other.
• Iterate all the numbers between given smallest and greatest number. In our above example between 1 to 6 and 14 to 20.
• Next do XOR with both results which gives the missing number

Lets see simple Java code implementation

```public class FindingMissingNumber {

public static void main(String[] args) {

int[] arr = new int[]{11,12,13,15,16,17,18,19};
int sr = 11;
int er = 19;

FindingMissingNumber obj = new FindingMissingNumber();

System.out.println("Missing number using XOR : "+obj.findMissingNumberUsingXOR(arr, sr, er));
}

public int findMissingNumberUsingXOR(int[] arr, int sr, int er){

int xor = 0;
int actualXor = 0;

for(int i=0;i<arr.length;i++){
xor = xor ^ arr[i];;
}

for(int i=sr;i<=er;i++){
actualXor = actualXor ^ i;
}

return (xor ^ actualXor);
}
}
```

OUTPUT:

```Missing number using XOR : 14
```