268. Missing Number

📝 Problem Details

• Title: 268. Missing Number
• Link: https://leetcode.com/problems/missing-number/
• Difficulty: Easy
• Tags/Categories: Math Arrays Sorting

💭What Were My Initial Thoughts?

- array is not sorted 
- if we sort the array, then check that the current index and the next index dont differ by 1, then we continue
- if it doesnt, then we know thats the element to return 

- came up with the idea that we can sum all the elements in the array, and create a separate sum for all numbers in the range of the starting number and n, return the diff between the two 

🤔What Did I Struggle With?

~

💡 Explanation of Solution

both of the inutitions work

⌛ Complexity Analysis

Sorting Approach:
	Time Complexity: O(n log n)
	Space Complexity: O(1) if we use the sort array

Math Approach:
	Time Complexity: O(n)
	Space Complexity: O(1)

💻 Implementation of Solution (Sorting Approach)

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        // Sort the array
        sort(nums.begin(), nums.end());
 
        // Check for missing number
        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] - nums[i-1] != 1) {
                return nums[i-1] + 1; // Return the missing number
            }
        }
 
        // If no missing number is found, check edge cases
        if (nums[0] != 0) return 0; // If the array doesn't start with 0
        if (nums.back() != nums.size()) return nums.size(); // If the array doesn't end with n
 
        return -1; // This line won't be reached if input is valid
    }
};

💻 Implementation of Solution (Math Approach)

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        
        int n = nums.size();
        int Tsum = (n*(n+1))/2;
        return  Tsum - accumulate(nums.begin(),nums.end(),0);
        
    }
};