codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
// Find all changed number in rank array containing roll numbers // Input an array containing n elements // These elements are numbered 1 to n // Some elements have changed (not 1 to n), find them // Function prototype: void printMissing(int *arr, int n); #include <iostream> #include <cstdlib> #include <vector> #include <cassert> using namespace std; /** * @brief printMissing prints the list of roll numbers that were affected by noise * @param [in] arr Rank list containing the list of all ranks such that arr[rank-1] = roll number * @param [in] sz Size of rank list array (5 <= rank_list <= 100) */ void printMissing(int *arr, int sz) { // assert(sz > 0); // cout << "DEBUG:: Input array = {" << arr[0]; // for(int i = 1; i < sz; ++i) cout << ',' << ' ' << arr[i]; // cout << '}' << endl; for(int i = 0; i < sz; ++i) { int expectedIndex = arr[i] - 1; while( (i != expectedIndex) && (expectedIndex <= sz) && (arr[expectedIndex] != arr[i]) ) { swap(arr[i], arr[expectedIndex]); expectedIndex = arr[i] - 1; } } for(int i = 0; i < sz; ++i) { if(i != arr[i] - 1) cout << "Distorted by noise: " << (i + 1) << endl; } } int main() { srand(20120609); const int nMinElementCount = 5; const int nMaxElementCount = 100; const int nMaxNoiseAffect = 15; const int sz = nMinElementCount + rand() % (nMaxElementCount - nMinElementCount + 1); vector<int> arr(sz); cout << "Info:: Size of array = " << sz << endl; for(int i = 0; i < sz; ++i) arr[i] = i + 1; const int changeCount = rand() % nMaxNoiseAffect; cout << "Info:: Maximum elements affected by noise = " << changeCount << endl; cout << endl; for(int i = 0; i < changeCount; ++i) arr[rand() % sz] = rand() % 1000; random_shuffle( arr.begin(), arr.end() ); printMissing( &arr[0], static_cast<int>( arr.size() ) ); return 0; }
Private
[
?
]
Run code
Submit