HackerRank Making Candies problem solution

In this HackerRank Making Candies problem solution, Karl loves playing games on social networking sites. His current favourite is CandyMaker, where the goal is to make candies.

Karl just started a level in which he must accumulate n candies starting with m machines and w workers. In a single pass, he can make m x w candies. After each pass, he can decide whether to spend some of his candies to buy more machines or hire more workers. Buying a machine or hiring a worker costs p units, and there is no limit to the number of machines he can own or workers he can employ.

Karl wants to minimise the number of passes to obtain the required number of candies at the end of the day. Determine the number of passes.

Function Description

Complete the minimumPasses function in the editor below. The function must return a long integer representing the minimum number of passes required.

minimumPasses has the following parameter(s):

• m: long integer, the starting number of machines
• w: long integer, the starting number of workers
• p: long integer, the cost of a new hire or a new machine
• n: long integer, the number of candies to produce

HackerRank Making Candies problem solution in Python.

#!/bin/python3

import math
import os
import random
import re
import sys

# Complete the minimumPasses function below.
def minimumPasses(m, w, p, n):
    days = 0
    candies = 0
    answer = math.ceil(n / (m * w))

    while days < answer:
        if p > candies:
            daysNeeded = math.ceil((p - candies) / (m * w))
            candies += daysNeeded * m * w
            days += daysNeeded

        diff = abs(m - w)
        available = candies // p
        purchased = min(diff, available)

        if m < w:
            m += purchased
        else:
            w += purchased

        rest = available - purchased
        m += rest // 2
        w += rest - rest // 2
        candies -= available * p

        candies += m * w
        days += 1

        remainingCandies = max(n - candies, 0)
        answer = min(answer, days + math.ceil(remainingCandies / (m * w)))
    
    return answer

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

    mwpn = input().split()

    m = int(mwpn[0])

    w = int(mwpn[1])

    p = int(mwpn[2])

    n = int(mwpn[3])

    result = minimumPasses(m, w, p, n)

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

    fptr.close()

Making Candies problem solution in Java.

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 {

    // Complete the minimumPasses function below.
    static long minimumPasses(long m, long w, long p, long n) {
        long candies = 0;
        long invest = 0;
        long spend = Long.MAX_VALUE;

        while (candies < n) {
                // preventing overflow in m*w
                long passes = (long) (((p - candies) / (double) m) / w);

                if (passes <= 0) {
                        // machines we can buy in total
                        long mw = candies / p + m + w;
                        long half = mw >>> 1;
                        if (m > w) {
                                m = Math.max(m, half);
                                w = mw - m;
                        } else {
                                w = Math.max(w, half);
                                m = mw - w;
                        }
                        candies %= p;
                        passes++;
                }

                // handling overflowing
                // if overflowing is encountered -> candies count are definitely more than long
                // thus it is more than n since n is long
                // so we've reached the goal and we can break the loop
                long mw;
                long pmw;
                try {
                        mw = Math.multiplyExact(m, w);
                        pmw = Math.multiplyExact(passes, mw);
                } catch (ArithmeticException ex) {
                        // we need to add current pass
                        invest += 1;
                        // increment will be 1 because of overflow
                        spend = Math.min(spend, invest + 1);
                        break;
                }

                candies += pmw;
                invest += passes;
                long increment = (long) Math.ceil((n - candies) / (double) mw);
                spend = Math.min(spend, invest + increment);
        }

        return Math.min(spend, invest);
}

    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[] mwpn = scanner.nextLine().split(" ");

        long m = Long.parseLong(mwpn[0]);

        long w = Long.parseLong(mwpn[1]);

        long p = Long.parseLong(mwpn[2]);

        long n = Long.parseLong(mwpn[3]);

        long result = minimumPasses(m, w, p, n);

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

        bufferedWriter.close();

        scanner.close();
    }
}

Problem solution in C++ programming.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

bool check(ll machines, ll workers, ll price, ll target, ll rounds) {
    if (machines >= (target+workers-1)/workers) return true;
    ll cur = machines*workers;
    rounds--;
    if (rounds == 0) return false;
    while (1) {
        ll rem = target - cur;
        ll rnds = (rem + machines*workers - 1) / (machines*workers);
        if (rnds <= rounds) return true;
        if (cur < price) {
          rem = price - cur;
          rnds = (rem + machines*workers - 1) / (machines*workers);
          rounds -= rnds;
          if (rounds < 1) return false;
          cur += rnds * machines * workers;
        }
        cur -= price;
        if (machines > workers) {
          workers++;
        } else {
          machines++;
        }
    }
    return false;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    ll m, w, p, n;
    cin >> m >> w >> p >> n;
    ll a = 1, b = 1000000000000LL;
    while (a < b) {
        ll mid = (a + b) >> 1;
        if (check(m, w, p, n, mid)) {
          b = mid;
        } else {
          a = mid + 1;
        }
    }
    cout << a << "n";
    return 0;
}