Solution to Codility Peaks problem.
First, we need to find all the peaks. Simply iterate through all elements and aggregate all the peaks into \(P\).
Then, we can iterate through the various possible group sizes \(g \in [1,N]\). We need the least \(g\) such that \(g | N\) (then \(\frac{N}{g}\) is maximized) and so that every group of size \(g\) has at least one peak. This can be done by simply iterating through all the peaks \(p \in P\) and checking if every has peak. The 100/100 Java code:
import java.util.*;
class Solution {
public int solution(int[] A) {
int N = A.length;
// Find all the peaks
ArrayList<Integer> peaks = new ArrayList<Integer>();
for(int i = 1; i < N-1; i++){
if(A[i] > A[i-1] && A[i] > A[i+1]) peaks.add(i);
}
for(int size = 1; size <= N; size++){
if(N % size != 0) continue; // skip if non-divisible
int find = 0;
int groups = N/size;
boolean ok = true;
// Find whether every group has a peak
for(int peakIdx : peaks){
if(peakIdx/size > find){
ok = false;
break;
}
if(peakIdx/size == find) find++;
}
if(find != groups) ok = false;
if(ok) return groups;
}
return 0;
}
}