(UVA) Popes - Solution 2

If you want to see another solution for this problem, click here.

For this solution I used Binary Search.

The complexity of this solution is O(N log N), which is better than the previous solution.


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

class Main  {
    public static int[] electionYears;
    public static int lastYearPeriod;
   
    public static int binSearch(int lo, int hi) {
        if (lo > hi) {
            return hi;
        }
       
        int mi = (lo+hi)/2;
        if (electionYears[mi] > lastYearPeriod) {
            return binSearch(lo, mi-1);
        }
        else if (electionYears[mi] < lastYearPeriod) {
            return binSearch(mi+1, hi);
        }
        else {
            return binSearch(mi+1, hi);
        }
    }
   
    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());
            electionYears = new int[numPopes];
            for (int i = 0; i < numPopes; i++) {
                electionYears[i] = Integer.parseInt(br.readLine());
            }
           
            int maxPopes = 0;
            int firstYearMax = 0;
            int lastYearMax = 0;
            for (int i = 0; i < numPopes; i++) {
                int firstYear = electionYears[i];
                lastYearPeriod = firstYear+period-1;
                int indexLastPopePeriod = binSearch(i, numPopes-1);
                int numPopesPeriod = indexLastPopePeriod-i+1;
                if (numPopesPeriod > maxPopes) {
                    maxPopes = numPopesPeriod;
                    firstYearMax = firstYear;
                    lastYearMax = electionYears[indexLastPopePeriod];
                }
            }
           
            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);
    }
}