O(n) time 36 ms O(1) space cpp solution


  • 2
    K

    We use arithmetic progression sum formula for searching missing number.
    E. g. sum of "0 1 2 3 4 5 6 7 .... n-1 n" is (0 + n) * (n + 1) / 2.
    Missing number wouldn't be added, so we get it by subtraction expected sum from computed.

    int missingNumber(vector<int>& nums) {
        int sum(0);
        for(int x : nums)
            sum += x;
        return (nums.size() * (nums.size() + 1))/2  - sum;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.