C++ summation and compare with nums, O(n)time, O(1)space


  • 0
    X

    try just compare 2 elements next to each other, yet it will not working if array not sorted.
    then try the summation:

    class Solution {
    public:
        int missingNumber(vector<int>& nums) {
            int sz = nums.size(); 
            if(sz < 1) return 0; 
            
    /*===============================================================================
        V 1.1 : after seeing discuss, find out add them together then substruct nums.
        Time:   O(n),    space: O(1) 
    *///=============================================================================
            int sum = (0 + sz) * (sz+1) / 2;
            int sumInVtr = 0; 
            for(int i = 0; i < sz; i++) sumInVtr += nums[i]; 
            return sum - sumInVtr; 
            
    /*===============================================================================
        V 1.0 : use num[i+1] - num[i] == 1 ? to see which one is missing.
        Time:   O(n),    space: O(1)    BUG: if array didnt sort, this not working.
    *///=============================================================================
    /*        if(sz == 1) return nums[0]==0 ? 1 : 0; 
            for(int i = 0; i < sz; i++){ // now at least has 2 nums in vector.
                if(i < sz-1){
                    if(nums[i+1] - nums[i] > 1) return nums[i]+1; 
                } else {
                    return nums[i] + 1; 
                }
            }
    */        
            return 0;
        }
    };
    

Log in to reply
 

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