class Solution {
public:
    int duplicateInArray(vector<int>& nums) {
        int n = nums.size();
        int a[n] = {0};
        for(int i=0; i<n; i++)
            a[nums[i]]++;
        for(int i=0; i<n; i++)
            if(a[i] > 1)
                return i;
    }
};

class Solution {
public:
    int duplicateInArray(vector<int>& nums) {
        int n = nums.size();        
        int l = 1, r = n;
        while(l < r)
        {
            int mid = l + r >> 1; 
            int count = 0;          
            for(int i=0; i<n; i++)
            {
                if(l <= nums[i] && nums[i] <= mid)
                    count++;
            }
            if(count > mid - l + 1)
                r = mid;
            else 
                l = mid + 1;
        }
        return l;
    }
};