HackerRank Goodland Electricity problem solution

In this HackerRank Goodland Electricity problem solution, 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.

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)

{"mode":"full","isActive":false}

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

{"mode":"full","isActive":false}

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;
}

{"mode":"full","isActive":false}

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("%d\n", counter);
    else
        puts("-1");

    return 0;
}

{"mode":"full","isActive":false}