```// Duplicate.cpp
//
// You have an array of n integers, randomly ordered, each with a value between 1 and (n-1).
// The array is such that there is one and only one value that occurs twice.
// Write a function that returns the repeated value.  You may not call any C library functions.
//
// Sample input:  [4 1 3 2 1]
//
// Correct sample output:  1
//
//

// ----- includes -----
#include <iostream>
#include "duplicate.h"

using namespace std;

// ----- defines -----

// ===== function prototypes =====

// ====== duplicate() =====
// finds the only duplicate integer from an array of N elements given that there are
// ints between 1 and (N-1) in this array and also given that there is only 1 duplicate
// int.
//
// Inputs : int ary[] - int array
//          int len   - N
// Outputs : the duplicate int or -1 if none is found
//
// Methodology - we use the fact that there are only 1..(N-1) ints in this array and
// also the knowledge that in C/C++ array's start with index 0. we check the 0th element
// with the [0th] element as index, until we locate the duplicate.
//
int duplicate(int ary[], int len) {

if (len <= 1) return -1;	// if array contains only 1 num

int i, nextIndex = ary;
int found = -1;;
int count = 0;

for (i=1; ((-1 == found) && (i<len)); ) {

if (ary[nextIndex] == ary[i]) {
found = ary[nextIndex];
} else {
nextIndex = ary[nextIndex];
i++;
}
count++;
}
#if DEBUG == 1
cout << "Found : " << found << " " << ary[i] << " : " << count << endl;
#endif
if (-1 != found) return found;
return -1;
}``` 