[[duplicate.cpp]]
Differences
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++]] | ||
