Naive Approach:

A naive approach could be to count all elements and store them in an array, and when we encounter any element which is occurring more than one then we return it.
This solution takes O(n) time and O(n) auxiliary space.

Pseudo Code

This Program returns duplicate element in an array

function repeatedNumber ( Arguement givenArray ){

   Define an array "count" of size (givenArray - 1)
   Initialize all elements of count with 0
   traverse the givenArray and increase the count of elements
   of givenArray corresponding to that index number in count array
   If(count[iterator] > 1){
     return count[iterator]
   }
   return -1
}

C++ Function Implementation

int repeatedNumber(const vector<int> &A) {
  vector<int> count(A.size()-1, 0);
  for(int i = 0 ; i < A.size() ; i++){
    count[A[i]-1]++;
    if(ret[ A[i] - 1 ] > 1) return A[i];
  }
  return -1;
}

Optimised Approach

Approach uses Floyd's Tortoise and Hare Algorithm

• Form following nested sequence using function "f(x) = A[x]" starting with index "x = 0"

  A[0], A[A[0]], A[A[A[0]]], A[A[A[A[0]]]],. . . . . . . .

• Each member in the sequence is an element of A[]
• This sequence will form a cycle if there is a duplicate element in the array with duplicate element entry point to the cycle

Sample Array



Cycle Formed in Array


• traversal starts from "A[0] = 3" and it enters cycle through "A[3] = 4"
• The Algorithm has two traversal variables called Hare and Tortoise, Hare being fast and Tortoise slow

  Hare = A[A[Hare]]
  Tortoise = A[Tortoise]

• Hare is fast so it enters the cycle first and Tortoise enters later
• Since, Hare is fast so it completes cycle before Tortoise and itersects with it at some point middle in array
• Now, move tortoise to the starting point of sequence and leave Hare within the cycle
• Both move with same speed i.e., "Hare = A[Hare]" and "Tortoise = A[Tortoise]"
• They will intersect at duplicate element
• Stop when they intersect and you have the duplicate element

Pseudo Code

function repeatedNumber ( Arguement givenArray ){

• Initialize Tortoise and Hare Variables with first element of givenArray
• Loop until we find the intersection point of Hare and Tortoise
•     define speed of Hare and Tortoise
•     Hare = givenArray[givenArray[Hare]]
•     Tortoise = givenArray[Tortoise]
•     Exit Loop when Hare == Tortoise
• Move Tortoise to start of givenArray
• Loop until Tortoise is not equal to Hare
•     Exit Loop when Tortoise == Hare
• return Tortoise

}

C++ Function Implementation

int repeatedNumberOptimized(int arr[]) {
  int Tortoise = arr[0];
  int Hare = arr[0];
  while (1) {
    Tortoise = arr[Tortoise];
    Hare = arr[arr[Hare]];
    if (Tortoise == Hare)
      break;
  }
  Tortoise = arr[0];
  while (Tortoise != Hare) {
    Tortoise = arr[Tortoise];
    Hare = arr[Hare];
  }
  return Tortoise;
}

Program Code

#include <iostream>
#include <algorithm>
#include <vector>

using std::cin;
using std::cout;
using std::endl;
using std::vector;

int repeatedNumber(const vector<int> &A) {
  vector<int> count(A.size()-1, 0);
  for(int i = 0 ; i < A.size() ; i++){
    count[A[i]-1]++;
    if(ret[ A[i] - 1 ] > 1) return A[i];
  }
  return -1;
}

int main(){

  int n, temp;
  vector<int> A;
  cin >> n;

  for( int i = 0; i < n; i++ ){
    cin >> temp;
    A.push_back(temp);
  }

  cout << repeatedNumber(A) << endl;
  return 0;
}