Problem
Here is my code. Let me describe what I do here. I have 7kg soaps, and 2kg soaps. And I have total kg that mean how many kg soaps I need. I should use 7kg soaps first, if there is no need I shouldn’t use 2 kg soaps. If I don’t use any 2kg soaps, it must return -1, if I use 2 kg soaps it must return the amount of how many of them I use. I have prepareCargoPacket(int 7kg soap, int 2 kg soap, int totalKg).
For example, prepareCargoPacket(2,2,16); return 1s since I use 2kg soaps one time. prepareCargoPacket(1,3,10); returns -1 because I can’t get 10kg from these values, and I can’t use 2kg soaps
package com.bit32.cargocalculation;
public class CargoCalculation {
/**
* Returns how many 2Kgs soap we need to use
*
* @param count7Kg -> count of how many 7Kgs soaps we have
* @param count2Kg -> count of how many 2Kgs soaps we have
* @param totalKg -> the needed Kg I have to get
* @return
*/
public int prepareCargoPacket(int count7Kg, int count2Kg, int totalKg) {
int solution = -1; // if there is no answer, or no need for 2Kgs soaps, the answer is -1
// if we have 7Kg ones many more than totalKg, we should decrease it to get from 2Kgs.
if (7*count7Kg > totalKg) {
return prepareCargoPacket(count7Kg-1, count2Kg, totalKg);
// if we have enough 7Kgs that are equal to totalKg, we will not use 2Kgs.
} else if (7*count7Kg == totalKg) {
return solution; // solution = -1
// if we have 7Kgs less than totalKg
} else {
// currentTotalKg is equal to the amount of Kg that we can use for 2Kgs
int currentTotalKg;
for (int i = count7Kg; i>=0; i--) {
currentTotalKg = totalKg - 7*i;
if (currentTotalKg % 2 == 0 && count2Kg*2 >= currentTotalKg) {
solution = currentTotalKg/2;
break;
}
return solution;
}
}
return solution;
}
Solution
First of all, your code doesn’t actually work for some cases. The return statement in the for loop causes the loop to only ever run once. This means your function doesn’t find a solution for prepareCargoPacket(2, 10, 12) (it tries with 1 7kg soap, fails the if check since 5 isn’t a multiple of 2, then returns -1 without ever trying with no 7kg soaps). Removing that return fixes it.
Another thing I want to point out is that your way to cap the number of 7kg soaps is really not very efficient. If you need to make a total weight of 6kg when you have 200000 7kg soaps available, your function will call itself 200000 times. This is not ideal, for multiple reasons. Not only is it a lot of steps (each of which takes some amount of time), but the program will also internally keep track of each function call in the call stack, and that thing can only get so big before your program crashes with a java.lang.StackOverflowError.
A way around that is to notice that if you have more than totalKg / 7 7kg soaps, the total weight is already too high. So if you have too many 7kg soaps at the start, you don’t need to keep trying with 1 less each time, because totalKg / 7 just gives you a nice upper bound.
To finish off with some nitpicking, I’m not a huge fan of repeating the weights of the soaps all over the place like that. If the person who wants this software comes up to you and says “Hi, sorry, we switched from 7kg soaps to 5kg soaps, can you update the program for us?” it would be annoying to replace the weight everywhere, and there’d be a risk of missing a place. A nicer approach could be replacing the numbers with constant variables, maybe something like final int HEAVY_WEIGHT = 7; and final int LIGHT_WEIGHT = 2;? That way, if the weights need changing, it only happens in one place. At that point I might also look into renaming the input parameters to something like heavyAvailable and lightAvailable to match those while I’m at it.
A few more thoughts
I looked some more, and came up with a few more comments.
Apart from the issue with there possibly being a lot of function calls, having the function call itself at all feels like it makes the logic a bit harder to follow. I’d like to restructure it so that that isn’t necessary, with that initial check being used not to re-enter the function, but to determine where the loop starts.
Another, fairly minor issue is that this function keeps going for longer that it might have to even though it should know it won’t find a solution. For example, if called as prepareCargoPacket(5, 0, 36) we get to the loop, notice we don’t have enough 2kg soaps to reach the weight of 1kg that’s missing. But then we continue to check if we can make 8kg instead. Which we can’t since we have too few soaps. So we go on to check 15kg instead. But we can’t make that either, so we check if we can make 22kg… Now imagine if instead of starting at 5 and 36 we’d started at something like 142,857,142 and 1,000,000,000.
Well, you don’t have to imagine. I tested it, and it was still really fast. Never underestimate a computer’s ability to do math quickly. Still, it can matter if the loop contains anything more complicated than a few basic math operators and a few ifs, so I’m bringing it up for future reference anyway. I also feel like switching the loop condition to take that into account also makes the code a bit cleaner, but it also arguably becomes a bit less obvious why it’s written the way it is, so it might not actually be an improvement.
The solution variable doesn’t seem entirely necessary to be honest. Each time the function returns, it either returns -1, or it changes solution for the first time and then immediately returns. At that point, I might get rid of that variable to save the reader from having to keep track of whether it’s been updated. That’s a matter of taste, though, there are definitely people who’d disagree with me on that.
Finally, since I’ve already done some nitpicking about variable names, I might as well complain about the last few. totalKg doesn’t feel as descriptive as it could be. It and currentTotalKg are also a bit confusable, because “the total” and “the current total” don’t really feel all that distinct to me – while that is sometimes the best way to describe two values, we might want to look for something that makes their purposes even more obvious. Going by what they’re doing, totalKg might be more accurately described as the goalWeight or targetWeight, and since currentTotalKg is the amount we’re missing to be able to reach that we might call that missingWeight or remainingWeight perhaps?
Taking all that into account, I might write something a bit like
package com.bit32.cargocalculation;
public class CargoCalculation {
public static final int HEAVY_WEIGHT = 7;
public static final int LIGHT_WEIGHT = 2;
/**
* Calculates how many lightweight soaps we need to use to reach exactly the target weight, if possible
* If no lightweight soaps are required, or if the target weight can't be reached, returns -1
*
* @param heavyAvailable The number of heavy soaps that can be used
* @param lightAvailable The number of light soaps that can be used
* @param targetWeight The desired sum of the weights of all the soaps
* @return
*/
public int prepareCargoPacket(int heavyAvailable, int lightAvailable, int targetWeight) {
int maxHeavyUsed;
if (HEAVY_WEIGHT * heavyAvailable > targetWeight) {
maxHeavyUsed = targetWeight / HEAVY_WEIGHT;
} else {
maxHeavyUsed = heavyAvailable;
}
// Loop until we find a solution, or until we know we can't
for (int remainingWeight = targetWeight - HEAVY_WEIGHT * maxHeavyUsed;
remainingWeight <= LIGHT_WEIGHT * lightAvailable;
remainingWeight += HEAVY_WEIGHT) {
if (remainingWeight == 0) {
// Special case: We have to return -1 if we don't need light soaps
return -1;
} else if (remainingWeight % LIGHT_WEIGHT == 0 &&
lightAvailable * LIGHT_WEIGHT >= remainingWeight) {
return remainingWeight / LIGHT_WEIGHT;
}
}
// No solution
return -1;
}
}
Though as I said if you think it’s clearer to write the loop as for (int i = maxHeavyUsed; i >= 0; i--) (and then define remainingWeight inside the loop), you can do that instead.