Differences

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

Link to this comparison view

duplicate.cpp [2014/10/26 01: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++]]
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