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

• 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);
}
}``````

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

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

• 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.

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

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

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