> For the complete documentation index, see [llms.txt](https://llssff.gitbook.io/coding-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://llssff.gitbook.io/coding-problems/unsorted-array/find-missing-number.md).

# Find missing number

In an **Unsorted Array** size N - 1 of 1 to N, find the missing number in O(n) time

**Solution 1**: HashMap

Average case: O(N)

Worst Case: O(N^2)

**Solution 2:** Boolean Array

input:     7   2   4   1  5   3

boolArr: 1? 2? 3? 4? 5? 6? 7?

Total num = input.length + 1 = 7

```
Boolean[] boolArr = new Boolean[input + 1];
Arrays.fill(array, Boolean.FALSE);

for (int cur: input){
    boolArr[cur - 1] = true; //int 7 -> boolArr[6] = true
}
for (int i = 0; i < boolArr.length; i++){
    if (boolArr[i] == false) System.out.println(i + 1);
}
```

**Time Comp:** O(traverse input + traverse boolArr) = O(2N) = (N)

**Solution 3:** Subtract

```
int sum = 0;
for (int i = 1; i <= input.length + 1; i++){
    sum += i;
}

int cursum = 0;
for (int i: input){
    cursum += i
}

return sum - cursum;
```

**Time Comp**: O(traverse input + add 1->N) = O(N + N) = O(2N) = O(N)

**Solution 4:** XOR

```
  public int missing(int[] array) {

    if (array.length == 0) return 1; 

    //XOR method 
    int x1 = array[0];
    int x2 = 1;
    int n = array.length;

    //XOR input array 1 -> n
    for ( int i = 1; i < n; i++){
      x1 = x1 ^ array[i];
    }

    //XOR ideal array 1 -> n + 1
    for (int i = 2; i <= n + 1; i++){
      x2 = x2 ^ i;
    }

    return (x1 ^ x2);
  }
```

**Time Comp:** O(One traversal + N XOR in x2) = O(2N) = O(N)

Space Comp: O(1)