This shows you the differences between two versions of the page.
— |
duplicate.cpp [2014/10/25 21:52] (current) |
||
---|---|---|---|
Line 1: | Line 1: | ||
+ | <code lang="cpp"> | ||
+ | // 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; | ||
+ | } | ||
+ | </code> | ||
+ | |||
+ | ---- | ||
+ | * [[cplusplus|Back to C++]] |