HackerRank Goodland Electricity problem solution

In this HackerRank Goodland Electricity problem solution, Goodland is a country with a number of evenly spaced cities along a line. The distance between adjacent cities is 1 unit. There is an energy infrastructure project planning meeting, and the government needs to know the fewest number of power plants needed to provide electricity to the entire list of cities. Determine that number. If it cannot be done, return -1.

You are given a list of city-data. Cities that may contain a power plant have been labeled 1. Others not suitable for building a plant are labeled 0. Given a distribution range of k, find the lowest number of plants that must be built such that all cities are served. The distribution range limits supply to cities where the distance is less than k.

Function Description

Complete the pylons function in the editor below.

pylons has the following parameter(s):

• int k: the distribution range
• int arr[n]: each city’s suitability as a building site

Returns

• int: the minimum number of plants required or -1

HackerRank Goodland Electricity problem solution in Python.

import math

def get_min(x,k,lights):
        
    best = -1
    best_ind=None
    for ind,i in enumerate(lights):
        #if abs(x - i)<k:
        if -k < x - i < k:
            best=i
            best_ind=ind
        elif i>x+k:
            break
    return best,best_ind

for qu in [1]:
    N,k = list(map(int,(input().strip().split(' '))))

    lights = list(map(int,(input().strip().split(' '))))
    assert(N==len(lights))
    lights = [i for i,val in enumerate(lights) if val==1]
    
    pos=0
    best=None
    best_ind=None
    count=0
 
    while 1:                                
            
        if pos>=N:
            break
        
        if best==lights[-1]:
            count=-1
            break
                       
        if best_ind==None:
            best,best_ind = get_min(pos,k,lights)
        else:
            lights = lights[(best_ind+1):]
            best,best_ind = get_min(pos,k,lights)
        
        if best==-1:
            count=-1
            break
        
        count+=1
        pos = best + k                                            

    
    print(count)

Goodland Electricity problem solution in Java.

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

public class Solution {

    public static void main(String[] args) throws IOException {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[]line = br.readLine().split(" ");
        int n = Integer.parseInt(line[0]);
        int k = Integer.parseInt(line[1]);
        line = br.readLine().split(" ");
        boolean[]light = new boolean[n];
        for(int i=0;i<n;i++){
            light[i] = line[i].equals("1");
        }
        
        k = k-1;
        
        int result = 0;
        int last = -1;
        int index = k;
        while(index < n){
            while(index>-1 && !light[index]){
                index--;
            }
            if(index == -1 || index <= last){
                System.out.println(-1);
                return;
            }
            result++;
            last = index;
//            System.out.println(last);
            index += k*2+1;
        }
        
        if(last+k+1 < n){
            result++;
            boolean l = false;
            for(int i=light.length-1;i>=light.length-k-1;i--){
                if(light[i]){
                    l = true;
                    break;
                }
            }
            if(!l){
                System.out.print(-1);
                return;
            }
        }
        
        System.out.println(result);
        
        
    }
}

Problem solution in C++.

#include <iostream>
#include <vector>

using namespace std;

int n, k;

vector<bool> bm;

int solve()
{
	int res = 0;
	for (int i = 0; i < n;)
	{
		int j = i + k - 1;
		for (; j + k > i; --j)
		{
			if (bm[j + k])
				break;
		}
		if (j + k == i)
		{
			return -1;
		}
		++res;
		i = j + k;
	}
	return res;
}

int main(int argc, char* argv[])
{
	ios::sync_with_stdio(false);

	cin >> n >> k;

	bm.resize(n + 2 * k);
	for (int i = 0; i < n; ++i)
	{
		int curr;
		cin >> curr;
		bm[k + i] = !!curr;
	}
	int res = solve();

	cout << res << endl;

	return 0;
}

Problem solution in C.

#include <stdio.h>
#include <stdbool.h>


int main(void) {
    int n, k;
    scanf("%d %d", &n, &k);

    int current_dist = 0;
    int available = -1;
    int counter   = 0;
    bool failed   = false;
    for(int i = 0; i < n; i++) {
        int temp;
        scanf("%d", &temp);

        if(!failed) {
            if(temp)
                available = i;
            
            if(current_dist == k - 1 && available != -1) {
                current_dist = -(k - 1 - (i - available));
                available    = -1;
                counter++;
            } else if(current_dist > k - 1) {
                failed = true;
            } else {
                current_dist++;
            }
        }
    }

    if(current_dist > 0)
        counter++;

    if(!failed)
        printf("%dn", counter);
    else
        puts("-1");

    return 0;
}