{"post":"

Brute Force Approach

Sort the given array and run a loop to find the duplicate number.

TC – O(nlogn) | SC – O(1)

Better Approach

Using HashMap

Initialize an empty hashmap.
Iterate over the elements of the array.
For each element, increase its occurrence count in the hashmap by 1.
Iterate over the elements of the hashmap.
For each element in the hashmap, check if its occurrence count is greater than 1. If it is, print the element as a duplicate.
If no duplicates are found, print a message indicating this.

TC – O(n)

SC – O(n)

Optimal Approach

Using Floyd Cycle detection

$\"\"$

We will take two pointers one will move fast and one slow.

#include<bits/stdc++.h>\nusing namespace std;\n\nint findDuplicates(int arr[], int arrSize){\n\tint fast = 0,\n      \tslow = 0;\n  \tdo{\n     \tslow = arr[slow];\n        fast = arr[arr[fast]];\n     \n    } while(slow != fast);\n\n  \tslow = 0;\n  \twhile(slow != fast){\n\t\tslow = arr[slow];\n        fast = arr[fast];\n    }\n  \t\n  \treturn slow; //or fast\n}\n\nint main(){\n  \tint arrWithDuplicates[] = {2,5,1,1,4,3};\n  \tint arrSize = sizeof(arrWithDuplicates)/sizeof(arrWithDuplicates[0]);\n  \tcout<<findDuplicates(arrWithDuplicates, arrSize);\n\treturn 0;\n}\n

Output

1\n

TC – O(n)

SC – O(1)

\n","title":"Find duplicate number in array","authorDetails":{"name":"studymite","slug":"admin"},"description":"Learn how to write a program in C++ to find duplicate numbers in an array using a hashmap. Find out how to use a hashmap to store the occurrence counts of each element in the array and how to iterate over the hashmap to identify and print duplicate numbers.","slug":"find-duplicate-number-in-array/","articleId":"636a83417bb1ce5072622b0b","bookmarkStatus":{"isBookmarked":false,"bookmarkId":null}}