3 lines of code , O(n) solution , with no extra space or variables


  • 1
    A

    The numbers are from 1 to N and indices are from 0 to N , the idea is to put each number into the corresponding index , like num[i] goes to num[num[i]] , but a number at index zero will be overlapping with some number in the same index and that number is the duplicate.

    Edit : I assumed the array could be changed hence i came up with this solution , i felt like sharing it anyway ,so i posted it here.

    class Solution {
    public:
        int findDuplicate(vector<int>& nums) {
            while(nums[nums[0]] != nums[0])
                swap(nums[0],nums[nums[0]]);
            return nums[0];
        }
    };
    

  • 0
    This post is deleted!

  • 0
    A

    @zachluna you are right, i found it later, i felt like sharing it anyway ,so i posted it here.


  • 0
    N
    This post is deleted!

Log in to reply
 

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