# Differences

This shows you the differences between two versions of the page.

 — duplicate.cpp [2014/10/25 21:52] (current) Line 1: Line 1: + ​ + // 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; + } + ​ + + ---- + * [[cplusplus|Back to C++]] 