Codility: Peaks Solution
Task
A[P – 1] < A[P] > A[P + 1]].:A non-empty array A consisting of N integers is given.
A peak is an array element which is larger than its neighbors. More precisely, it is an index P such that
0 < P < N − 1, A[P − 1] < A[P] and A[P] > A[P + 1].…
We want to divide this array into blocks containing the same number of elements. More precisely, we want to choose a number K that will yield the following blocks:
A[0], A[1], …, A[K − 1], A[K], A[K + 1], …, A[2K − 1], … A[N − K], A[N − K + 1], …, A[N − 1].What’s more, every block should contain at least one peak. Notice that extreme elements of the blocks (for example A[K − 1] or A[K]) can also be peaks, but only if they have both neighbors (including one in an adjacent blocks).
The goal is to find the maximum number of blocks into which the array A can be divided.
…
Write a function:
int solution(vector<int> &A);that, given a non-empty array A consisting of N integers, returns the maximum number of blocks into which A can be divided.
If A cannot be divided into some number of blocks, the function should return 0.
For example, given:
A[0] = 1 A[1] = 2 A[2] = 3 A[3] = 4 A[4] = 3 A[5] = 4 A[6] = 1 A[7] = 2 A[8] = 3 A[9] = 4 A[10] = 6 A[11] = 2the function should return 3, as explained above.
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [1..100,000];
- each element of array A is an integer within the range [0..1,000,000,000].
Solution
#include <math.h>
#include <vector>
int solution(vector<int> &A) {
vector<ulong> peaks;
ulong N = A.size();
vector<ulong> entries[N];
if (N <= 2)
return 0;
// build list of peaks
int last = A[1], prelast = A[0];
for (ulong i = 2; i < N; i++) {
if ((last > A[i]) && (last > prelast))
peaks.push_back(i – 1);
prelast = last;
last = A[i];
}
/* for each block size: build array of flags, one for each block,
* showing if there is a peak in the block
*/
for (ulong i = 1; i <= N; i++) {
if (N % i == 0) {
entries[i – 1].resize(N / i);
for (ulong j = 0; j < entries[i – 1].size(); j++)
entries[i – 1][j] = false;
for (ulong pos : peaks)
entries[i – 1][trunc(pos / i)] = true;
}
}
for (ulong i = 1; i <= N; i++) {
if (N % i == 0) {
bool allFound = true;
for (ulong j = 0; j < entries[i – 1].size(); j++) {
if (!entries[i – 1][j]) {
allFound = false;
break;
}
}
// iterating up block size so first found is the result
if (allFound)
return N / i;
}
}
return 0;
}Test Function
This code tests the solution
int main() {
vector<int> A0{1, 2, 3, 4, 3, 4, 1, 2, 3, 4, 6, 2};
assert(solution(A0) == 3);
vector<int> A1{};
assert(solution(A1) == 0);
// 1 peak
vector<int> A3{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 10};
assert(solution(A3) == 1);
// no peak
vector<int> A2{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};
assert(solution(A2) == 0);
// end values not peaks
vector<int> A4{1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2};
assert(solution(A4) == 4);
// prime size
vector<int> A5{1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1};
assert(solution(A5) == 1);
}Results
Codility Results
O(N * log(log(N))) in fact it is O(N√N) assuming even distribution of peaks| Correctness | 100% |
| Performance | 100% |
| Time Complexity | O(N√N) |