(UVA) Popes - Solution 1

For this problem we had to use Binary Search to find the answer. Firstly, I tried to solve it without using it; however, the complexity of such solution was O(N^2).


import java.io.*;
import java.util.*;

class Main  {
    public static void process() throws NumberFormatException, IOException {  
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       
        String line = br.readLine();
        while (line != null) {
            if (line.equals("")) {
                line = br.readLine();
            }
           
            int period = Integer.parseInt(line);
            int numPopes = Integer.parseInt(br.readLine());
            int[] electionYears = new int[numPopes];
            for (int i = 0; i < numPopes; i++) {
                electionYears[i] = Integer.parseInt(br.readLine());
            }
           
            int oldK = -1;
            int maxPopes = -1;
            int firstYearMax = -1;
            int lastYearMax = -1;
            for (int i = 0; i < numPopes; i++) {
                int k = electionYears[i];
                if (k == oldK) {
                    continue;
                }
                int countPopes = 0;
                int lastYearPope = -1;
                for (int j = i; j < numPopes; j++) {
                    if (electionYears[j] > (k+period-1)) {
                        break;
                    }
                    countPopes++;
                    lastYearPope = electionYears[j];
                }
                if (countPopes > maxPopes) {
                    maxPopes = countPopes;
                    firstYearMax = k;
                    lastYearMax = lastYearPope;
                }
                oldK = k;
            }
           
            System.out.println(maxPopes + " " + firstYearMax + " " + lastYearMax);

            line = br.readLine();
        }
                                                
        return;
    }
  
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();

        System.exit(0);
    }
}