Simple java solution with explanation (time:O(n), space:O(1))


  • 3
    H
    public int missingNumber(int[] nums) {
        int sum = 0, len = nums.length;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
        }
        return (len*(len+1)/2 - sum);
    }
    

    • The basic idea is using the sum:
    • see some examples firstly:
    • 0 1 2 3 4 5 (0+n-1)n/2=sum=(0+n)(n+1)/2-miss
    • 0 1 2 (3) 4 5 6 (0+n)(n+1)/2-miss=sum or 1 2 3 4 5 6
      In any case, missing element is in the middle, at the beginning or at the end of the array, the missing element can be found by "miss = n(n+1)/2 - sum"

  • 1
    L

    {tag = 1;} , tag wasn't used anywhere else. And you should use long to avoid integer overflow.


  • 0
    H

    forget to delete tag, thx for reminding.


  • 0
    L

    And if ((len - 1)*len/2 == sum) {
    return len;
    } this line could be covered by your last return line :)


  • 0
    F

    The place of the missing element does not matter. What you are implementing here is the Gaussian addition formula to add numbers from 1..n. which is actually n*(n-1) /2.
    In this case, you are using the length of the array as the determinant for N. However, we know that the array is missing one member for sure, which means that the real length if the array was full would be nums.length + 1... hence your formula turns into calculating the total by n * (n+1) /2.
    By that token, you are also guaranteed to find the missing value if you added all the numbers in the supposedly full array and subtracted the total from this array.
    As someone else also pointed out, you don't need the if statement before the return line. The last line is always going to give you the right answer.


  • 0
    H

    Yep, you are right. thank you!! I have edited it.


Log in to reply
 

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