Java solution O(1) space and O(n) in time


  • 51
    K

    Pretty simple since we are told that we are missing only one number in [1,n], we just need to look at the difference between the sum([1,n]) = n * (n+1) / 2 and the sum of nums in our array.

    public class Solution {
        public int missingNumber(int[] nums) {
            int sum = 0;
            for(int num: nums)
                sum += num;
                
            return (nums.length * (nums.length + 1) )/ 2 - sum;
        }
    }
    

    With a slight mod to the return statement the situation for large n is taken care of. The needed modification is

    return ( (nums.length * (nums.length + 1) ) - 2 * sum ) / 2;

  • 4
    J

    pretty concise solution, here is c++ version

    class Solution {
    public:
        int missingNumber(vector<int>& nums) {
            int ret = (nums.size() + 1) * nums.size() /2;
            for(auto i: nums)
                ret -= i;
            return ret;
        }
    };

  • 0
    W

    pretty solution!


  • 3
    J

    it will overflow when n is large


  • 0

    Nice implmentation by reversing summation to subtraction :-)


  • 0
    K

    Actually This code will still produce the right answer since sum will also overflow so when we subtract those two overflown numbers we end up with the right answer.


  • 4

    @kevin36 You forgot about the /2. Try for example nums=[1,2,3,...,70000]. Your code returns -2147483648 instead of 0.


  • 0
    K

    @ StefanPochmann Yes you are right and I was wrong, thank you for pointing that out to me.

    Although changing the return statement to ( (nums.length * (nums.length + 1) ) - 2 * sum ) / 2; fixes the problem.


  • 0

    Nice implmentation.


  • 0

    Ha, nice and clever fix. Although won't work if let's say the missing number is 1.1 billion. But at least here at LeetCode, that won't happen.


  • 9
    C

    we can do the following to avoid the overflow.

    public class Solution {
        public int missingNumber(int[] nums) {
            int n = nums.length;
            int basic;
            int sum = 0;
            if(n%2 == 0) basic =n/2;   //according to the formula n*(n+1)/2, if n is even, add n/2 for n+1 times, otherwise, add (n+1)/2 for n times;
            else basic = (n+1)/2;
            for(int i=0;i<n;++i)
            {
                sum = sum + basic - nums[i];
            }
            if(n%2 == 0) sum += basic;
            return sum;
        }
    }

  • 0
    B

    public class Solution {
    public int missingNumber(int[] nums) {
    int result = 0;
    for(int i = 0; i < nums.length; i++){
    result += i + 1 - nums[i];
    }
    return result;
    }
    }


  • 0
    B
    public class Solution {
    public int missingNumber(int[] nums) {
        int result = 0;
        for(int i = 0; i < nums.length; i++){
            result += i+1-nums[i];
        }
        return result;
    }
    

    }


  • -1
    R

    lol~ we got the same idea~


  • 0
    S

    Really clever!


  • 0

    You deserve more up votes.


  • 7
    J

    Using the XOR operator is the simplest way to avoid overflow and get the answer.

    int xor = 0;
    for (int i=0; i<nums.length; i++) {
       xor = xor ^ nums[i] ^ (i+1);
    }
    return xor;
    

    this is possible because XOR operation btw the same numbers is 0, and the values and indices of the array are same except the missing value.


  • 0
    B

    brilliant answer


  • -1
    R

    public static int findMissingNo(int [] nums){
    int res=0;
    for (int i = 0; i < nums.length; i++) {
    res= i+1 -nums[i];
    if(res !=0)
    return nums[i]-1;
    }
    return res;

    }


  • 0
    V

    @CYFCYF Wow.. Really like your approach. Such clever workarounds give the readers new ways to think.


Log in to reply
 

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