TopCoder SRM 701 SortingSubsets

TopCoder Statistics - Problem Statement

This problem is short. Note that we just need to count the count of number's positions to change. We don't care the number of moves we did. So we sort the original array, compare it to the original array. If the number at the same position is not same, we know that that number at the position was changed. So time complexity is O(N).

#include <bits/stdc++.h>

using namespace std;

class SortingSubsets {
 public:
  int getMinimalSize(vector<int> a) {
    vector<int> c(a);
    sort(c.begin(), c.end());
    int cnt = 0;
    for (int i = 0; i < int(c.size()); ++i) {
      cnt += (c[i] == a[i] ? 0 : 1);
    }
    return cnt;
  }
};

int main(void) {
  SortingSubsets a;
  vector<vector<int> > v(4);
  v[0] = { 3, 2, 1};
  v[1] = {1, 2, 3, 4};
  v[2] = {4, 4, 4, 3, 3, 3};
  v[3] = {11, 11, 49, 7, 11, 11, 7, 7, 11, 49, 11};

  for (auto vv : v) {
    cout << a.getMinimalSize(vv) << endl;
  }
  
  return 0;
}