Codility-CPP/MaxCounters.cpp at master · andrewlin94/Codility-CPP · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include "all.h"

// 100% Correctness + 100% Performance = 100% Task Score
// Time Complexity O(M+N)
vector<int> solution(int N, vector<int> &A) {
  vector<int> counters;
  for (unsigned int i = 0; i != N; ++i) {
    counters.push_back(0);
  }
  int currentMin = 0;
  int currentMax = 0;
  for (auto it = A.begin(); it != A.end(); ++it) {
    if (*it > N) {  // A[i] > X, max counter
      currentMin = currentMax;
    }else { // A[i] <= N, increase counter[*it - 1];
      if (counters[*it - 1] < currentMin) { // Check if the current element is equal to the minimum (if max counter was called)
        counters[*it - 1] = currentMin;
      }
      ++counters[*it - 1];
      if (counters[*it - 1] > currentMax) { // Keep track of the current maximum
        currentMax = counters[*it - 1];
      }
    }
  }
  // Put max on counters that were never called from vector A.
  for (auto it = counters.begin(); it != counters.end(); ++it) {
    if (*it < currentMin) {
      *it = currentMin;
      }
  }
  return counters;
}

/*
100% Correctness + 0% Performance = 44% Task Score
Time Complexity O(M*N)
vector<int> solution(int N, vector<int> &A) {
    vector<int> counters;
    for (unsigned int i = 0; i != N; ++i) {
        counters.push_back(0);
    }
    for (auto it = A.begin(); it != A.end(); ++it) {
        if ((*it) > N) {
            for (auto cIt = counters.begin(); cIt != counters.end(); ++cIt) {
                int max = *max_element(counters.begin(), counters.end());
                (*cIt) = max;
            }
        }else {
            ++counters[(*it)-1];
        }
    }
    return counters;
}
*/

/*
100% Correctness + 40% Performance = 66% Task Score
Time Complexity O(M*N)
vector<int> solution(int N, vector<int> &A) {
    vector<int> counters;
    for (unsigned int i = 0; i != N; ++i) {
        counters.push_back(0);
    }
    for (auto it = A.begin(); it != A.end(); ++it) {
        if ((*it) > N) {
          int max = *max_element(counters.begin(), counters.end());
            for (auto cIt = counters.begin(); cIt != counters.end(); ++cIt) {
                (*cIt) = max;
            }
        }else {
            ++counters[(*it)-1];
        }
    }
    return counters;
}
*/

int main(void) {
  vector<int> A = {3, 4, 4, 6, 1, 4, 4};
  cout << "Expected [ 3 2 2 4 2 ]. Solution gives ";
  vector<int> answer = solution(5, A);
  cout << "[ ";
  for (int x : answer) {
    cout << x << " ";
  }
  cout << "]" << endl;
  return 0;
}