// 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;
}

Info:: Size of array = 53
Info:: Maximum elements affected by noise = 3

Distorted by noise: 26
Distorted by noise: 30
Distorted by noise: 51