## fizzbuzzer

### 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: 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));
}
}