// 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[0];
	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;
}

duplicate.cpp.txt · Last modified: 2014/10/26 01:52 (external edit)
CC Attribution-Share Alike 3.0 Unported
www.chimeric.de Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0