Lecture 48 :- Find Duplicate Number

To find a duplicate number in an array, you can use various approaches depending on the constraints and requirements of the problem. Here are three common methods to find a duplicate number in an array:

1. Using Hash Set: You can use a hash set to keep track of elements seen so far while traversing the array. If an element is already in the hash set, it means it is a duplicate.

Here's the C++ code to find the duplicate number using a hash set:

cppCopy code

#include <iostream> #include <vector> #include <unordered_set> int findDuplicate(std::vector<int>& nums) {    std::unordered_set<int> seen;    for (int num : nums) {        if (seen.count(num) > 0) {            return num;        }        seen.insert(num);    }    return -1; // No duplicate found } int main() {    std::vector<int> nums = {1, 3, 4, 2, 2};    int duplicate = findDuplicate(nums);    if (duplicate != -1) {        std::cout << "Duplicate number: " << duplicate << std::endl;    } else {        std::cout << "No duplicate found." << std::endl;    }    return 0; }

1. Using Sorting: Sort the array first, and then traverse it to find adjacent elements with the same value. The duplicate number will be found during the traversal.

Here's the C++ code to find the duplicate number using sorting:

cppCopy code

#include <iostream> #include <vector> #include <algorithm> int findDuplicate(std::vector<int>& nums) {    std::sort(nums.begin(), nums.end());    for (int i = 1; i < nums.size(); i++) {        if (nums[i] == nums[i - 1]) {            return nums[i];        }    }    return -1; // No duplicate found } int main() {    std::vector<int> nums = {1, 3, 4, 2, 2};    int duplicate = findDuplicate(nums);    if (duplicate != -1) {        std::cout << "Duplicate number: " << duplicate << std::endl;    } else {        std::cout << "No duplicate found." << std::endl;    }    return 0; }

1. Using Floyd's Tortoise and Hare Algorithm (Cycle Detection): If the array contains elements from 1 to n, you can treat the array as a linked list, where the value of each element represents the next index. In this case, there will be a cycle if there is a duplicate element.

Here's the C++ code to find the duplicate number using Floyd's Tortoise and Hare Algorithm:

cppCopy code

#include <iostream> #include <vector> int findDuplicate(std::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; } int main() {    std::vector<int> nums = {1, 3, 4, 2, 2};    int duplicate = findDuplicate(nums);    if (duplicate != -1) {        std::cout << "Duplicate number: " << duplicate << std::endl;    } else {        std::cout << "No duplicate found." << std::endl;    }    return 0; }

All three methods can effectively find a duplicate number in an array. The choice of the method depends on the specific problem constraints and requirements.