Given a vector of integers, we want to split it in the maximum numbers of same-sized blocks, such as any block would contain at least one peak (aka local maximum).
The problem, part of the Codility Prime and composite numbers section, is not complicated, however I needed to spend some time thinking over it to understand what really was its point. As usual, I found helpful writing test cases, here are a few of them:
TEST(Peaks, Given) // 1
{
std::vector<int> input { 1, 2, 3, 4, 3, 4, 1, 2, 3, 4, 6, 2 };
ASSERT_EQ(3, solution(input));
}
TEST(Peaks, ThreeSpikes) // 2
{
std::vector<int> input { 0, 1, 0, 0, 1, 0, 0, 1, 0 };
ASSERT_EQ(3, solution(input));
}
TEST(Peaks, ElevenSaw) // 3
{
std::vector<int> input { 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0 };
EXPECT_EQ(1, solution(input));
}
TEST(Peaks, TwelveSaw) // 4
{
std::vector<int> input { 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1 };
EXPECT_EQ(4, solution(input));
}
TEST(Peaks, NoPeak) // 5
{
std::vector<int> input(10);
std::iota(input.begin(), input.end(), 1);
ASSERT_EQ(0, solution(input));
}
TEST(Peaks, MaxPlain) // 6
{
std::vector<int> input(100000);
for(unsigned i = 1; i < input.size(); i += 2)
input[i] = 1;
ASSERT_EQ(25000, solution(input));
}
1. Codility provided test case. In this case the smallest size we can chose to have subsequences of the same size, each of them containing a peak, is four. Leading to a solution of 3.
2. Very plain case. Three blocks sized three are the optimal solution.
3. The input sequence is sized 11. That is, a prime number, we can't find any subinterval in this case, we just have to check if there is at least a peak, to decide to return 0 or 1.
4. Twelve could be split in 2, 3, 4, 6 sized units.
5. I have used iota() to generate a monotone function. No peak in it.
6. This test case is to check the algorithm performance. It should be easy to see that the minimum acceptable block size is four (two won't work because of the last interval).
Here is my C++11 solution:
int solution(std::vector<int>& input)
{
if(input.size() < 3) // 1
return 0;
std::vector<unsigned> peaks(input.size() + 1); // 2
for(std::size_t i = 1; i < input.size() - 1; ++i)
{
if(input[i] > input[i - 1] && input[i] > input[i + 1])
peaks[i+1] = 1;
}
std::partial_sum(peaks.begin(), peaks.end(), peaks.begin());
for(std::size_t size = 3; size <= input.size() / 2; ++size) // 3
{
if(input.size() % size) // 4
continue;
bool hasPeaks = true;
for(std::size_t end = size; end < peaks.size(); end += size) // 5
{
if(peaks[end - size] == peaks[end])
{
hasPeaks = false;
break;
}
}
if(hasPeaks) // 6
return input.size() / size;
}
return peaks.back() ? 1 : 0; // 7
}
1. Get rid of trivial cases.
2. I am going to use partial sum to check if there is any peak in a give interval (some more detail on this STL function and its mathematical meaning in a previous post). To simplify the code, I add a spurious element at the beginning, set to zero, and shift all the partial sums one position to the right.
3. Check all the possible subsequence, from 3 to half the size of the input sequence. It won't make sense to check for subsequences sized less than three, since it is not possible to conceive a to have a local maximum in this case - see comments for more details.
4. We want all-equal blocks, so we accept only sizes that are divisor of the input sequence size.
5. Check all the subsequence to ensure they contain at least a peak.
6. If the current block size is good, return the number of them in the input sequence.
7. We couldn't find any way of splitting the sequence, return 1 if there is at least a peak, 0 otherwise.
Go to the full post
