Looking for good programming challenges?

Use the search below to find our solutions for selected questions!

Goodland Electricity challenge – O(n)

Sharing is caring!

In the previous post I discussed an algorithm that had a running time of \mathcal{O}(n^2). Well here is an \mathcal{O}(n) algorithm to the Goodland Electricity challenge.

Greedy algorithm

  1. For each city i store its preceding tower in previousTowerFor[i]. If i has a tower then previousTowerFor[i] = i. If no tower precedes, set to -1. For example for input: 0 1 1 1 1 0, previousTowerFor will be: -1 1 2 3 4 4
  2. Iterate over all cities i.
    • Get the nearest possible tower x using previousTowerFor. The right-most tower can at most have distance i + k - 1. So looking at the previousTowerFor[i + k - 1] can either result at a tower to the right of i (within k distance) or to a tower to the left of i (if the last preceding tower of index i + k - 1 happens to be one on the left of i).
    • If no such tower exists or distance of tower to city is \ge k, return -1. Else go to next uncovered city i = x + k.
    • For the next uncovered city (which is x + k), the next possible tower will be at index \textless x + k + k (k-1 coverage from x plus 1 for the next city plus k-1 coverage from the next tower). See illustration below:
      goodland_electricity_1

Solution

public class GoodlandElectricity {

    private static int solve(int n, int k, boolean[] hasTower) {
        int count = 0;

        int[] previousTowerFor = new int[n]; // previousTowerFor[i] holds index of the preceding tower or i if i is a tower.
        int last = -1;
        for (int i = 0; i < n; i++) {
            if (hasTower[i]) {
                last = i;
            }
            previousTowerFor[i] = last;
        }

        int city = 0;
        while (city < n) {
            // A tower can be at most k - 1 distance from city. When looking at previousTowerFor[city + k - 1]
            // we get the right-most tower from city (since previousTowerFor[city + k - 1] holds the latest tower to the left of index city + k - 1).
            int tower = previousTowerFor[Math.min(city + k - 1, n - 1)];

            if (tower == -1 | city - tower >= k) {
                return -1;
            } else {
                // We found a tower within k distance of city.
                // Jump to next city that requires a tower. Since tower can cover k-1 cities, we jump to city = tower + k.
                city = tower + k;
                count++;
            }

        }

        return count;
    }

    public static void main(String[] args) throws FileNotFoundException {
        System.setIn(new FileInputStream(System.getProperty("user.home") + "/" + "in.txt"));
        Scanner in = new Scanner(System.in);

        int n = in.nextInt();
        int k = in.nextInt();

        boolean[] hasTower = new boolean[n];
        for (int i = 0; i < n; i++) {
            int t = in.nextInt();
            hasTower[i] = t == 1;
        }

        System.out.println(solve(n, k, hasTower));
    }
}