Easiest C++ Solution (5 Lines)


  • 0
    S

    The following code is done in max O(n) time and without any extra space.

    It uses a simple idea based on the constraint given that for an array with n+1 elements, each element can have a value between 1 to n. So we can store the occurrence of a number in that array itself.

    Consider the example,
    If you find 1 in somewhere in the array. You can simply make the value of a[1] negative. This will give you a count that you have seen a "1" in the array. Now whenever you get "1" again in the array and when you try to check a[1] ..... it will already be negative confirming that it is the element which is the duplicate

    Sometime you will come at element which is already made negative by someone before(meaning that its index is the number which is already observed). Hence you have to take abs to handle that.

    int findDuplicate(vector<int>& nums) {
            
            for(int i=0;i<nums.size();i++){
                
                if(nums[abs(nums[i])] < 0)
                    return abs(nums[i]);
                
                    nums[abs(nums[i])]*= -1;
            }
            return 0;
        } 
    

  • 0
    S

    @sohammehta Hope you like the solution


Log in to reply
 

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