Header Ad

HackerRank Minimum Time Required problem solution

In this HackerRank Minimum Time Required Interview preparation kit problem you need to complete the minimumTimefunction.


HackerRank Minimum Time Required solution


Problem solution in Python programming.

#!/bin/python3

import math
import os
import random
import re
import sys

# Complete the minTime function below.
def minTime(machines, goal):
    machines, count = sorted(machines), len(machines)
    min_day = math.ceil(goal / count) * machines[0]
    max_day = math.ceil(goal / count) * machines[-1]

    while min_day < max_day:
        day = (max_day + min_day) // 2
        day_sum = sum(day // m for m in machines)

        if day_sum >= goal:
            max_day = day
        else:
            min_day = day + 1

    return min_day

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

    nGoal = input().split()

    n = int(nGoal[0])

    goal = int(nGoal[1])

    machines = list(map(int, input().rstrip().split()))

    ans = minTime(machines, goal)

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

    fptr.close() 



Problem solution in Java Programming.

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;

public class Solution {

   static long minTime(long[] machines, long goal) {

        Arrays.sort(machines); //sort the machine array
        long max = (machines[machines.length - 1]) * goal;
        long min = 0;
        long result = -1;
        //do a binary tree search
        while(max > min){
            long midValue = (max + min) / 2;
            long unit = 0;
            for(long machine : machines){
                unit += midValue / machine;
            } 

            if(unit < goal) {
                min = midValue + 1;
                result = midValue + 1;
            } else  {
                max = midValue;
                result = midValue; 
            } 


        }

        return result;


    }

    private static final Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) throws IOException {
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        String[] nGoal = scanner.nextLine().split(" ");

        int n = Integer.parseInt(nGoal[0]);

        long goal = Long.parseLong(nGoal[1]);

        long[] machines = new long[n];

        String[] machinesItems = scanner.nextLine().split(" ");
        scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

        for (int i = 0; i < n; i++) {
            long machinesItem = Long.parseLong(machinesItems[i]);
            machines[i] = machinesItem;
        }

        long ans = minTime(machines, goal);

        bufferedWriter.write(String.valueOf(ans));
        bufferedWriter.newLine();

        bufferedWriter.close();

        scanner.close();
    }
}


Problem solution in C++ programming.

#include <bits/stdc++.h>

using namespace std;

vector<string> split_string(string);

// Complete the minTime function below.
long minTime(vector<long> machines, long goal) {
    sort(machines.begin(),machines.end());
    long max = machines[machines.size()-1];
    long min = machines[0];
    long upper = (max * goal)/machines.size();
    long lower = (min * goal)/machines.size();
    long dia; 
    long produccion;
    while(upper>lower){
        dia = (upper + lower)/2;
        produccion = 0;
         for(long i = 0;i<machines.size();i++){  
           produccion+=dia/machines[i];
            
        }
         
         if(goal<= produccion){
             upper = dia;
         }else{
             lower= dia +1; 
         }
       
    }
    return lower;
    
}

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

    string nGoal_temp;
    getline(cin, nGoal_temp);

    vector<string> nGoal = split_string(nGoal_temp);

    int n = stoi(nGoal[0]);

    long goal = stol(nGoal[1]);

    string machines_temp_temp;
    getline(cin, machines_temp_temp);

    vector<string> machines_temp = split_string(machines_temp_temp);

    vector<long> machines(n);

    for (int i = 0; i < n; i++) {
        long machines_item = stol(machines_temp[i]);

        machines[i] = machines_item;
    }

    long ans = minTime(machines, goal);

    fout << ans << "\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;
}

Post a Comment

1 Comments

  1. The upper bound is wrong, I think this solution might cover all hackerrank's test cases, but consider a test case where machines = [3, 3, 3] and goal is 10
    For that, upper bound according to solution will be 10 days and lower bound will be 10 days, while loop doesn't run and it returns lower which is 10 days, but in 10 days it will not get completed, on 9th day, 9 items will be completed, but on 10th day nothing will be completed, the next set of items will only get completed on 12th day, so answer will be 12

    ReplyDelete