HackerRank Turn Off the Lights problem solution

In this HackerRank Turn Off the Lights problem solution There are n bulbs in a straight line, numbered from 0 to n-1. Each bulb has a button associated with it, and there is a cost, ci, for pressing this button. When some button i is pressed, all the bulbs at a distance <= k from bulb will be toggled(off->on, on->off).

Given n, k, and the costs for each button, find and print the minimum cost of turning off all n bulbs if they’re all on initially.

HackerRank Turn Off the Lights problem solution in Python.

#!/bin/python3

import os
import sys

def get_sum(s, c, k, t):
    v = None
    for p in range(s, len(c), 2 * k + 1):
        print(p, end=' ')
        if v:
            t += 2 * k + 1
        else:
            v = 0
            
        v += c[p]
        
    if t < len(c):
        v = None
        
    print(' => ', v, 't=', t)
    return v

#
# Complete the turnOffTheLights function below.
#
def turnOffTheLights(k, c):
    min_sum = None
    for s in range(k + 1):
        summ = get_sum(s, c, k, k + 1 + s)
        if not min_sum or (summ and min_sum > summ):
            min_sum = summ
        
    return min_sum

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

    n, k = map(int, input().split())
    c = list(map(int, input().rstrip().split()))

    result = turnOffTheLights(k, c)
    fptr.write(str(result) + 'n')
    fptr.close()

Turn Off the Lights problem solution in Java.

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

public class Solution {

  static long turnOffTheLights(int k, int[] arr) {
    long result = Long.MAX_VALUE;
    for(int beg = 1; beg <= 1 + k; beg++) {
        long cost = 0;
        int nxt = beg;
        while(nxt < arr.length) {
            cost += arr[nxt];
            nxt = nxt + 2 * k + 1;
        }
        nxt = nxt - 2 * k - 1;
        if(nxt + k >= arr.length-1) {
          result = Math.min(cost, result);
        }
    }
    return result;
  }

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

    StringTokenizer st = new StringTokenizer(br.readLine());
    int n = Integer.parseInt(st.nextToken());
    int k = Integer.parseInt(st.nextToken());

    int[] c = new int[n+1];
    st = new StringTokenizer(br.readLine());
    for (int cItr = 1; cItr <= n; cItr++) {
      int cItem = Integer.parseInt(st.nextToken());
      c[cItr] = cItem;
    }

    long result = turnOffTheLights(k, c);

    bw.write(String.valueOf(result));
    bw.newLine();

    bw.close();
    br.close();
  }
}

Problem solution in C++.

#include <bits/stdc++.h>

using namespace std;

vector<string> split_string(string);


long turnOffTheLights(int k, vector<int> c) {
    
    int n = c.size();
    long long best = 1000000000000000000;
    for (int f = 0; f <= min(k, n-1); ++f)
    {
        //cout << f << endl;
        long long price = 0;
        int i;
        for (i = f; i < n; i+=2*k+1)
        {
            price+=c[i];
            //cout << i << " ";
        }
        
        if (n - i + k  > 0)
        {
            //cout << "skipn";
            continue;
        }
        if (price < best)
            best = price;
    }
    
    return best;
}

int main()
{
    ofstream fout(getenv("OUTPUT_PATH"));

    string nk_temp;
    getline(cin, nk_temp);

    vector<string> nk = split_string(nk_temp);

    int n = stoi(nk[0]);

    int k = stoi(nk[1]);

    string c_temp_temp;
    getline(cin, c_temp_temp);

    vector<string> c_temp = split_string(c_temp_temp);

    vector<int> c(n);

    for (int c_itr = 0; c_itr < n; c_itr++) {
        int c_item = stoi(c_temp[c_itr]);

        c[c_itr] = c_item;
    }

    long result = turnOffTheLights(k, c);

    fout << result << "n";

    fout.close();

    return 0;
}

vector<string> split_string(string input_string) {
    string::iterator new_end = unique(input_string.begin(), input_string.end(), [] (const char &x, const char &y) {
        return x == y and x == ' ';
    });

    input_string.erase(new_end, input_string.end());

    while (input_string[input_string.length() - 1] == ' ') {
        input_string.pop_back();
    }

    vector<string> splits;
    char delimiter = ' ';

    size_t i = 0;
    size_t pos = input_string.find(delimiter);

    while (pos != string::npos) {
        splits.push_back(input_string.substr(i, pos - i));

        i = pos + 1;
        pos = input_string.find(delimiter, i);
    }

    splits.push_back(input_string.substr(i, min(pos, input_string.length()) - i + 1));

    return splits;
}

Problem solution in C.

#include <assert.h>
#include <limits.h>
#include <math.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char* readline();
char** split_string(char*);

/*
 * Complete the turnOffTheLights function below.
 */
long turnOffTheLights(int k, int c_count, int* c) {
    long totalcost[2*k + 1];
    for(int i = 0; i < 2*k + 1; i++){
        totalcost[i] = 0;
    }
    for(int i = 0; i < c_count; i++){
        totalcost[i%(2*k + 1)] = totalcost[i%(2*k + 1)] + c[i];
    }

    long max = LONG_MAX;
    int low = ((c_count - 1)%(2*k + 1) < k? 0 : (c_count - k - 1)%(2*k + 1));
    int high = ((c_count - 1)%(2*k + 1) > k? k : (c_count - 1)%(2*k + 1));
    

    for(int i = low; i <= high; i++){
        max = (totalcost[i] < max? totalcost[i] : max);
    }
    return max;
}

int main()
{
    FILE* fptr = fopen(getenv("OUTPUT_PATH"), "w");

    char** nk = split_string(readline());

    char* n_endptr;
    char* n_str = nk[0];
    int n = strtol(n_str, &n_endptr, 10);

    if (n_endptr == n_str || *n_endptr != '') { exit(EXIT_FAILURE); }

    char* k_endptr;
    char* k_str = nk[1];
    int k = strtol(k_str, &k_endptr, 10);

    if (k_endptr == k_str || *k_endptr != '') { exit(EXIT_FAILURE); }

    char** c_temp = split_string(readline());

    int c[n];

    for (int c_itr = 0; c_itr < n; c_itr++) {
        char* c_item_endptr;
        char* c_item_str = c_temp[c_itr];
        int c_item = strtol(c_item_str, &c_item_endptr, 10);

        if (c_item_endptr == c_item_str || *c_item_endptr != '') { exit(EXIT_FAILURE); }

        c[c_itr] = c_item;
    }

    long result = turnOffTheLights(k, n, c);

    fprintf(fptr, "%ldn", result);

    fclose(fptr);

    return 0;
}

char* readline() {
    size_t alloc_length = 1024;
    size_t data_length = 0;
    char* data = malloc(alloc_length);

    while (true) {
        char* cursor = data + data_length;
        char* line = fgets(cursor, alloc_length - data_length, stdin);

        if (!line) { break; }

        data_length += strlen(cursor);

        if (data_length < alloc_length - 1 || data[data_length - 1] == 'n') { break; }

        size_t new_length = alloc_length << 1;
        data = realloc(data, new_length);

        if (!data) { break; }

        alloc_length = new_length;
    }

    if (data[data_length - 1] == 'n') {
        data[data_length - 1] = '';
    }

    data = realloc(data, data_length);

    return data;
}

char** split_string(char* str) {
    char** splits = NULL;
    char* token = strtok(str, " ");

    int spaces = 0;

    while (token) {
        splits = realloc(splits, sizeof(char*) * ++spaces);
        if (!splits) {
            return splits;
        }

        splits[spaces - 1] = token;

        token = strtok(NULL, " ");
    }

    return splits;
}