Problem Statement
There are N pots. Every pot has some water in it. They may be partially
filled. So there is a Overflow Number O associated with every pot which tell how many minimum stone pieces are require for that pot to overflow. So if for a pot O-value is 5 it means minimum 5 stone pieces should be put in that pot to make it overflow.Initially a crow watched those pots and by seeing the water level he anticipated O-value correctly for every pot (that is he knew O1 to On). But when he came back in evening he found that every pot is painted from outside and he is not able to know which pot has what O-value. The Crow wants some K pots to overflow so that he can serve his child appropriately. For overflowing the pots he needs to search for the stones in forest (assume that every stone has same size).
He wants to use minimum number of stones to overflow the K pots. But he doesn't know now which pot has what O-value. So the task is to find out the minimum number of stones that the crow requires to make the K pots overflow in the worst case.
Input Specification:
- A array O corresponding to O-value of N pots {O1, O2, ....... , On}
- Number of pots
- K -value ( number of pots which the crow wants to overflow)
Output Specification:
Minimum number of stones required to make K pots overflow in worst case or -1 if input is invalid.
Example:
Let's say there are two pots:
- Pot 1 has O value of 5 , O1= 5
- Pot 2 has O value of 58, O2= 58
Let's say the crow wants to make one of the pots overflow. If he knows which pot has what O-value he would simply search for 5 stones and put them in pot 1 to make it overflow. But in a real case he doesn't know which pot has what O-value so just 5 stones may not always work. However he does know that one pot has O-value 5 and other has 58. So even in the worst case he can make one of the pot overflow just by using 10 stones. He would put 5 stones in one pot if it doesn't overflow he would try the remaining 5 in the other pot which would definitely overflow because one of the pot has O-value of 5. So the answer for above question is minimum 10 stones even in worst case.
Please let me know the corrections that I need to make the code better.
public class ThirstyCrow {
public ThirstyCrow() {
super();
}
private static final int INVALID_INPUT=-1;
public int getMinimumNumberOfStonesRequiredToOverflowThePots(int[] overflowValues,int numberOfPotsPresent,
int numberOfPotsToOverFlow){
List<Pot> pots = null;
if(overflowValues.length>numberOfPotsPresent)return INVALID_INPUT;
if(numberOfPotsPresent<numberOfPotsToOverFlow) return INVALID_INPUT;
try {
pots = Pot.createPotsFromOverFlowLimits(overflowValues, numberOfPotsPresent);
} catch (InvalidInputException e) {
return INVALID_INPUT;
}
return getTotalNumberOfStonesUsedForOverflowing(pots, numberOfPotsPresent, numberOfPotsToOverFlow);
}
private int getTotalNumberOfStonesUsedForOverflowing(List<Pot> pots,int numberOfPotsPresent,
int numberOfPotsToOverFlow){
int numberOfPotsOverFlown=0;
int totalNumberOfStonesUsedForOverflowing = 0;
while(numberOfPotsOverFlown!=numberOfPotsToOverFlow){
int minimumOverFlowValue = getMinimumOverFlowValue(pots) ;
addTheStonesToAllPots(pots, minimumOverFlowValue);
numberOfPotsOverFlown++;
totalNumberOfStonesUsedForOverflowing+=(minimumOverFlowValue*pots.size());
removeOverflowingPotFromTheList(pots);
}
return totalNumberOfStonesUsedForOverflowing;
}
private int getMinimumOverFlowValue(List<Pot> pots){
if(pots.isEmpty())return 0;
Collections.sort(pots);
return pots.get(0).numberOfStoneRequiredForOverFlow();
}
private void removeOverflowingPotFromTheList(List<Pot> pots){
if(pots==null) return;
Iterator<Pot> potsListIterator = pots.iterator();
while(potsListIterator.hasNext()){
Pot pot = potsListIterator.next();
if(pot.numberOfStoneRequiredForOverFlow()==0) potsListIterator.remove();
}
}
private void addTheStonesToAllPots(List<Pot> pots,int numberOfStonesToAdd){
if(pots==null) return;
for (Pot pot : pots) {
pot.addStonesToThePot(numberOfStonesToAdd);
}
}
}
class Pot implements Comparable<Pot>{
private int overflowValue;
private int numberOfStonesPresent=0;
public Pot(int overflowValue) throws InvalidInputException{
if(overflowValue<0) throw new InvalidInputException("Invalid Input Provided!!");
this.overflowValue=overflowValue;
}
public Integer getOverFlowValue(){
return overflowValue;
}
public Integer getNumberOfStonesPresent() {
return numberOfStonesPresent;
}
public void addStonesToThePot(int numberOfStones){
if(numberOfStonesPresent>=overflowValue) return; //If the Pot is Already overflowing
numberOfStonesPresent+=numberOfStones;
}
public Integer numberOfStoneRequiredForOverFlow(){
return overflowValue-numberOfStonesPresent;
}
@Override
public int compareTo(Pot pot) {
return this.numberOfStoneRequiredForOverFlow().compareTo(pot.numberOfStoneRequiredForOverFlow());
}
public static List<Pot> createPotsFromOverFlowLimits(int [] overFlowLimits,int numberOfPots) throws InvalidInputException{
List<Pot> pots = new ArrayList<>();
if(overFlowLimits==null || overFlowLimits.length==0) return pots;
for (int i = 0; i < numberOfPots; i++) {
pots.add(new Pot(overFlowLimits[i]));
}
return pots;
}
}
class InvalidInputException extends Exception{
private String message;
private static final long serialVersionUID = 8332397639526918252L;
public InvalidInputException(String message){
this.message=message;
}
public String getMessage() {
return message;
}
}