O(n) time O(1) space solution. Use long to cover corner cases if enough memory for large input


  • 2
    L

    Maybe it takes too much memory for the largest test case where nums.length = Integer.MAX_VALUE, so we could just use int sum, target to pass OJ.

    public class Solution {
        public int missingNumber(int[] nums) {
            long sum = 0, target = (long)nums.length*(long)(nums.length+1)/2;
            for(int i=0;i<nums.length;i++) sum += (long)nums[i];
            return (int)(target-sum);
        }
    }

  • 0

    Good point, and the problem actually starts a lot earlier.
    Already around sqrt(INT_MAX), because of the n*(n+1) calculation.


  • 0
    L

    Thank you. I learned a lot from you. :)


  • 0
    M

    I am wondering if you really need long. Maybe int is totally fine. If int overflow, the subtraction of two overflowed int should still be correct.


  • 0
    L

    Hi moyegej, thank you for your comment, it makes sense. :)


  • 0

    @moyegej You're overlooking the /2. Try input [1,2,3,...,47000]. With int, answer is -2147483648 instead of 0.


Log in to reply
 

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