!/bin/python3

import math import os import random import re import sys import bisect #

Complete the 'pylons' function below.

The function is expected to return an INTEGER.

The function accepts following parameters:

1. INTEGER k

2. INTEGER_ARRAY arr

def pylons(k, arr): n=len(arr) List=[] for i in range(n): if arr[i]==1: List.append(i) end=-1 ans=0 istart=0 while end

if name == 'main': fptr = open(os.environ['OUTPUT_PATH'], 'w')

first_multiple_input = input().rstrip().split()

n = int(first_multiple_input[0])

k = int(first_multiple_input[1])

arr = list(map(int, input().rstrip().split())) #ADITYA SHARMA

result = pylons(k, arr)

fptr.write(str(result) + '\n')

fptr.close()

3 months ago+ 0 comments

def main():
    import sys
    input = sys.stdin.read
    data = input().splitlines()
    
    n, k = map(int, data[0].split())
    light = list(map(int, data[1].split()))
    
    # Convert light array to boolean
    light = [True if x == 1 else False for x in light]
    
    k -= 1  # Adjust k to be zero-indexed
    
    result = 0
    last = -1
    index = k
    
    while index < n:
        while index >= 0 and not light[index]:
            index -= 1
        if index == -1 or index <= last:
            print(-1)
            return
        result += 1
        last = index
        index += k * 2 + 1
    
    if last + k + 1 < n:
        result += 1
        l = False
        for i in range(n - 1, n - k - 2, -1):
            if light[i]:
                l = True
                break
        if not l:
            print(-1)
            return
    
    print(result)

if __name__ == '__main__':
    main()

11 months ago+ 0 comments

Java

public static int pylons(int k, List<Integer> arr) {
        int ans = 0, n = arr.size();
        for(int i = 0; i < n; i++){
            
            // Power plant should be built on buildIdx
            int buildIdx = Math.min(i + (k - 1), n - 1);
            
            // Keep looking for a power plant
            while(buildIdx >= 0 && buildIdx < n && arr.get(buildIdx) == 0)
                buildIdx--;
                
            if(buildIdx >= 0 && buildIdx < n && arr.get(buildIdx) == 1 && Math.abs(buildIdx - i) < k){
                ans++; // Build here
                i = buildIdx + (k - 1);
            }
            else
                return -1;
        }
        return ans;
    }

1 year ago+ 0 comments

C#:

public static int pylons(int k, List<int> arr)
    {
        int p = -1;
        int count = -1;
        p = StartingKIndex(p, arr, k);
        if(p != -1)
        {
            p = MiddleIndexes(p, k, arr, out count);
        }
        if(count != -1 && (p + k - 1) < arr.Count - 1)
        {
            p = arr.Count - 1;
            count  = LastIndex(p, k, arr, count); 
        }
        return count;
    }
    
    public static int StartingKIndex(int p, List<int> arr, int k)
    {
        // Check the first city where Power plant can be built within the distribution range
        
        for(int i = k - 1; i >= 0; i--)
        {
            if(arr[i] == 1)
            {
                p = i; 
                break;
            }
        }
        
        return p;
    }
    
    public static int MiddleIndexes(int p, int k, List<int> arr, out int count)
    {   
        // StartIndex function will return a city index so make the count as 1 initially.
        count = 1;
        
        // Check for the next cities where Power plant can be built and increment the count
        while((p + (2 * k) - 1) < arr.Count)
        {
            bool flag = false;
            p = p + (2 * k) - 1;
            for(int i = p; i > p - (2 * k) + 1; i--)
            {
                if(arr[i] == 1)
                {
                    p = i;
                    count = count + 1;
                    flag = true;
                    break;
                }
            }
            
        // if a city cannot be covered withing the distribution range make the count as -1
            if(!flag)
            {
                count = -1;
                break;
            }
        }
        return p;
    }
    
    public static int LastIndex(int p, int k, List<int> arr, int count)
    {
     // find the last city where the power plant can be built within the distribution range.   
        
        bool flag = false;
        for(int i = p; i > arr.Count - k + 1; i--)
        {
            if(arr[i] == 1)
            {
                count += 1;
                flag = true;
                break;
            }
        }
        
        // if city is not found make the count as -1
        if(!flag)
        {
            count = -1;
        }
        return count;
    }

1 year ago+ 0 comments

My approach for this was essentially: given a city position, find the optimal point to place a power plant for that city position. Once I find a place for it, move to the furthest out city position not covered by the power plant I just placed, and do that again. Continue doing that until I reach the end of the array.

To find the optimal position for a given city, I use the k value to go as far out as possible (taking care to remain in-bounds of the array). I check if the position can contain a power plant. If it can, I use that position. If not, I reduce the value by one and continue. The lowest value is the previously placed power plant + 1 (or 0 if none has been placed yet).

Sort by

|

52 Discussions

|