HackerRank Goodland Electricity Problem Solution

In this post, we will solve 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 distance is less than k
Example
k=3
arr [0, 1, 1, 1, 0, 0, 0] =
Each city is 1 unit distance from its neighbors, and we’ll use ( based indexing. We see there are 3 cities suitable for power plants, cities 1, 2 and 3. If we build a power plant at arr[2], it can serve arr[0] through arr[4] because those endpoints are at a distance of 2 and 2 < k. To serve arr[6], we would need to be able to build a plant in city 4, 5 or 6. Since none of those is suitable, we must return-1. It cannot be done using the current distribution constraint

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

Input Format

The first line contains two space-separated integers n and k, the number of cities in Goodland and the plants’ range constant.
The second line contains n space-separated binary integers where each integer indicates suitability for building a plant.

Output Format

Print a single integer denoting the minimum number of plants that must be built so that all of Goodland’s cities have electricity. If this is not possible for the given value of K, print -1.

Sample Input

STDIN         Function
-----         --------
6 2           arr[] size n = 6, k = 2
0 1 1 1 1 0   arr = [0, 1, 1, 1, 1, 0]

Sample Output

Explanation

Cities c[1], c[2], c[3], and c[4] are suitable for power plants. Each plant will have a range of k = 2. If we build in cities 2 cities, c[1] and c[4], then all cities will have electricity.

Table of Contents

Goodland Electricity C Solution

#include<stdio.h>
int main ()
{
    int n,k,j,flag;
    scanf("%d%d",&n,&k);
    int tower[n],i;
    for(i=0;i<n;i++)
        scanf("%d",&tower[i]);
    int sol=-1,count=0,previ=0;
    for(i=0;i<n;i++)
    {
        if(i+k-1<n)
            j=i+k-1;
        else
            j=n;
        flag=0;
        for(j;j>=previ;j--)
        {
            if(tower[j]==1)
            {
                flag=1;
                break;
            }
        }
        if(flag==0)
            break;
        else
        {
            count++;
        }
        if(j+k-1<n)
           {
                i=j+k-1;
                previ=j+1;
           }
        else
            break;
        }
    if(flag)
        printf("%d\n",count);
    else
        printf("-1");
}

Goodland Electricity C++ Solution

#include <bits/stdc++.h>

typedef long long int64;
typedef unsigned long long uint64;

using namespace std;

inline bool covered(int &a, pair<int,int> &b) {
  return b.first <= a && a <= b.second;
}

int main(int argc, char* argv[]) {

    ios::sync_with_stdio(false);

    int n, k;
    cin >> n >> k;

    vector<pair<int,int>> cov;
    for (int i = 0; i < n; ++i) {
      int ax; cin >> ax;
      if (ax) {
        cov.push_back({max(0,i-k+1),min(n-1,i+k-1)});
      }
    }

    int cur = 0;
    int pos = 0;
    int sz = cov.size();
    int ans = 0;

    while ((pos < sz) && (cur < n)) {
      int far = cur;
      bool ok = false;
      while ((pos < sz) && covered(cur, cov[pos])) {
        far = max(far, cov[pos].second);
        ok = true;
        pos++;
      }
      if (ok) {
        cur = far+1;
        ans++;
      } else break;
    }

    if (cur < n) ans = -1;
    cout << ans << "\n";

    return 0;
}

Goodland Electricity C Sharp Solution

using System;
using System.Collections.Generic;
using System.IO;
class Solution {
    static void Main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution */
        string[] data = Console.ReadLine().Split(' ');
        int n = int.Parse(data[0]);
        int k = int.Parse(data[1]);
        bool[] cities = Array.ConvertAll(Console.ReadLine().Split(' '), x => int.Parse(x) == 1);
        
        int towers = 0;
        int i = 0;
        int lastT = 0;
        while (i < n)
        {
            int t = Math.Min(i + k - 1, n - 1);
            while(!cities[t] && t > lastT)
            {
                t--;
            }
            if (t == lastT && (t > 0 || !cities[t]))
            {
                Console.WriteLine(-1);
                return;
            }
            lastT = t;
            i = t + k;
            towers++;
        }
        Console.WriteLine(towers);
    }
}

Goodland Electricity Java Solution

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

Goodland Electricity JavaScript Solution

'use strict';

const fs = require('fs');

process.stdin.resume();
process.stdin.setEncoding('utf-8');

let inputString = '';
let currentLine = 0;

process.stdin.on('data', inputStdin => {
    inputString += inputStdin;
});

process.stdin.on('end', _ => {
    inputString = inputString.replace(/\s*$/, '')
        .split('\n')
        .map(str => str.replace(/\s*$/, ''));

    main();
});

function readLine() {
    return inputString[currentLine++];
}

// Complete the pylons function below.
function pylons(n, k, arr) {
     var reach = k-1;
     var count = 0;
  // start at first index
  var i = 0;
  while (i < arr.length) {
    var j = i + reach;
    while (arr[j] !== 1) {
      j --;
      if (i - reach - 1 === j) {   
        return -1;
      }
    }
    i = j + reach + 1;
    count ++;
  }
  return count;  
}

function main() {
    const ws = fs.createWriteStream(process.env.OUTPUT_PATH);

    const nk = readLine().split(' ');

    const n = parseInt(nk[0], 10);

    const k = parseInt(nk[1], 10);

    const arr = readLine().split(' ').map(arrTemp => parseInt(arrTemp, 10));

    let result = pylons(n, k, arr);

    ws.write(result + "\n");

    ws.end();
}

Goodland Electricity Python Solution

n,k=map(int,input().split())
arr=[int(x) for x in input().split()]
boolean=True
store=0
indices=[]
for x in range(n):
    if arr[x]==1:indices.append(x)
        
for i in range(k-1,-1,-1):
    if arr[i]==1:
        first=i
#        print(first)
        store+=1
        break
        
else:
    boolean=False
    print(-1)
       
if boolean:  
    while first<n-2*k:
        for x in range(first+2*k-1,first,-1):
            if arr[x]==1:
                first=x
                store+=1
#                print(first)
                break
        else:
            boolean=False
            print(-1)
            break
    if boolean:   
        if first+k>=n-1:
            print(store)    
        else:
            for x in range(n-1,n-k-1,-1):
                if arr[x]==1:
                    print(store+1)
                    break
            else:print(-1,"sdvss")