In this HackerRank Turn Off the Lights problem solution we have 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.
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()
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;
}