Question

Formatted question description: https://leetcode.ca/all/268.html

 268	Missing Number

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

 Example 1:

 Input: [3,0,1]
 Output: 2

 Example 2:

 Input: [9,6,4,2,3,5,7,0,1]
 Output: 8

 Note:
 Your algorithm should run in linear runtime complexity.

 Could you implement it using only constant extra space complexity?

 @tag-array
 @tag-bit

Algorithm

Use the summation formula of the arithmetic sequence to find the sum of all the numbers between 0 and n, and then traverse the array to calculate the cumulative sum of the given numbers, and then do the subtraction, the difference is the missing number.

Or, use bit. The idea is that since there is one missing number between 0 and n, XOR the complete array between 0 and n, and then the same number will become 0, and the rest is missing number.

Code

Java

  • 
    public class Missing_Number {
    
        class Solution {
            public int missingNumber(int[] nums) {
                int missing = nums.length; // @note: key, add highest number
                for (int i = 0; i < nums.length; i++) {
                    missing ^= i ^ nums[i];
                }
                return missing;
            }
        }
    }
    
  • // OJ: https://leetcode.com/problems/missing-number/
    // Time: O(N)
    // Space: O(1)
    class Solution {
    public:
        int missingNumber(vector<int>& A) {
            return (1 + A.size()) * A.size() / 2 - accumulate(begin(A), end(A), 0);
        }
    };
    
  • class Solution(object):
      def missingNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)
        return (n * (n + 1)) / 2 - sum(nums)
    
    

All Problems

All Solutions