Find the Duplicate Number [287] from Leetcode

We have been asked to return the integer that has been repeated. There could only be one number that has been repeated and only once.

In an array of length n+1, the elements are in the range [1, n].

They have specified that the original array should not be modified. This signifies that we should not use any sorting function.

---

So i stared at the screen for a while, unable to come up with any other method other than our friend nested loops. Hence, i looked up the solutions online and found out something about tortoise and hare or the slow and fast algorithm. There is another method too, but that one also employs two loops if we are talking about writing the code in C++. Nonetheless, I will write all the methods that i believe that i understood well enough.

Basic Nested Loop:

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

Time Complexity is O(n²).

Space Complexity is O(1).

Using a Count Array

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        vector<int> count(nums.size() - 1); // creating a count array of same lenght as the given array.
        for (int i = 0; i < nums.size(); ++i) {
            ++count[nums[i]]; // incrementing the value at the indice that represents the element in
// given array.
            if (count[nums[i]] > 1) { // if it is found that the value of element at the particular
// indice is greater than 1, it return the indice.
                return nums[i];
            }
        }
        return 0;
    }
};

Time Complexity is O(n).

Space Complexity is O(n). → Hence, this method is getting dropped. But its a fun technique though.

Using Addition

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int n = nums.size() - 1;
        int s = n * (n + 1)/2;
        int a = 0;
        for (int i : nums) {
            a += i;
        }
        return a - s;
    }
};

But our guy does not pass the third test case. Cuz, I assumed that the number is repeated only once.

Well, i was feeling smart until i executed it.

Hash Set

After looking through someone’s solution, they had Hash Set. I will add that here.

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        unordered_set<int> hashSet;
        for (int i : nums) {
            // gets the 'second' member of the returned pair of element 
            // and the bool by .insert()
            if (!hashSet.insert(i).second) {
                return i;
            }
        }
        return 0;
    }
};

Time Complexity is O(n).

Space Complexity is O(n). → Hence dropped.

This method uses the nature of a hash set to only have unique values.

Fast-Slow Approach

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int slow = nums[0];
        int fast = nums[0];

        do {
            slow = nums[slow];
            fast = nums[nums[fast]];
        } while (slow != fast);

        slow = nums[0];
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }

        return slow;
    }
};

Time Complexity is O(n).

Space Complexity is O(1).

→ Hence, this is our solution.

This is not an intuitive approach. I don’t think it would be possible for anyone to come up with this method within an hour.

I have this algorithm almost by-hearted now, without even intending to do so. Its just nice to look at.

To be honest, I will not tell you that I completely understand and attempt to to teach you what is going on. There were some great Youtube videos on this method, check em out.

---

Thanks for stickin around.