287. Find the Duplicate Number

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        
        for (int i = 0; i < n - 1; i++)
        {
            if(nums[i] == nums[i + 1])
                return nums[i];
        }
        
        return -1;
    }
};

// Time Complexity: O(nlogn)
// Space Complexity: O(n)

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        const int MX = 1e6 + 5;
        bitset<MX> mask;
        
        for (int i = 0; i < nums.size(); i++) {
            if (mask[nums[i]] == 1) 
                return nums[i];
            
            mask[nums[i]] = 1;
        }
        
        return 0;
    }
};