image

Photo Credit: Pixiv - 七淵

Missing Number

Posted on   |  

https://leetcode.com/problems/missing-number/

Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.

For example,
Given nums = [0, 1, 3] return 2.

Note:
Your algorithm should run in linear runtime complexity.

Solution 1: Binary Search

Time complexity: O(NlogN); Space Complexity O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public class Solution {
    public int missingNumber(int[] nums) {
        Arrays.sort(nums);
        if (nums.length == 1) {
            return nums[0] == 0 ? 1 : 0;
        }
        
        int end = nums.length - 1;
        int start = 0;
        
        while (start + 1 < end) {
            int mid = start + (end -start) / 2;
            if (nums[mid] == mid) {
                start = mid;
            } else {
                end = mid;
            }
        }
        
        if (nums[end] == end) {
            return nums[end] + 1;
        } else if (nums[end - 1] == end - 1){
            return end;
        } else {
            return end - 1;
        }
    }
}

Solution 2: Extra O(N) Space

Time complexity: O(N); Space Complexity O(N)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Solution {
    public int missingNumber(int[] nums) {
        int[] count = new int[nums.length + 1];
        for (int i = 0; i < nums.length; i++) {
            count[nums[i]]++;
        }
        for (int i = 0; i < count.length; i++) {
            if (count[i] == 0) {
                return i;
            }
        }
        return -1;
    }
}

Solution 3: Bit Manipulation

reference: http://believerw.github.io/2016/04/14/Bit-Manipulation/

Time complexity: O(N); Space Complexity O(1)

1
2
3
4
5
6
7
8
9
10
11
12
public class Solution {
    public int missingNumber(int[] nums) {
        int result = 0;
        for (int i = 0; i <= nums.length; i++) {
            result ^= i;
        }
        for (int i = 0; i < nums.length; i++) {
            result ^= nums[i];
        }
        return result;
    }
}

Solution 4: Method Without Bit Manipulation

reference: https://leetcode.com/discuss/96842/1ms-java-solution-without-bit-manipulation

Time complexity: O(N); Space Complexity O(1)

1
2
3
4
5
6
7
8
9
10
public class Solution {
    public int missingNumber(int[] nums) {
        int sum = 0, i = 0;

        for (; i < nums.length; i++)
            sum = sum + i - nums[i];

        return (sum + i);
    }
}