Assignment Description:

You are opening a restaurant that makes the BEST tomato soup. The secret of making the best

tomato soup is properly splitting up the ingredients in equal proportions. The most important

ingredient that needs to be evenly distributed are tomatoes. This tomato soup has spread

throughout the town that people are lining up just to have it$.$ Luckily, the kitchen you design has

an enormous stove that allows you to make $n$ tomato soups simultaneously. In other words, you

have $n$ pots to work with. Now unfortunately, your staff has made a tiny, but noticeable mistake.

As they were bringing out the pots to the stove, you noticed that the tomato proportions are way

off for each set of pots. You have lots of people lined up just to try this soup. You don't want one

pot to have more tomatoes than the other pots. That will throw off the tomato taste proportions.

You realize the only way of fixing the staff's mistake is to properly transfer the tomatoes to

neighboring pots as quickly as possible. The challenge is you must determine the number of

minimum moves needed to transfer the tomatoes over until all pots have the same exact

number of tomatoes. In order to solve this problem, you must use a greedy algorithm

technique.

We can represent the set of pots as an array of integers where each value contains the number of

tomatoes $($some can include the value $0).$ For example, the following figure shows an array with

three pots.

pots $\{\begin{array}{ccc}\text{:}[0,& 3,& 0]\end{array}$

The first and third $($indexes $0$ and $2)$ pots have $0$ tomatoes while the second pot has $3$ tomatoes.

Here, the minimum number of swaps needed to evenly distribute the tomatoes is $2.$ The

following figures show how the scenario would work out.

pots

Here, we moved $1$ tomato from index $1$ to index $0.$ The second move now is to move the extra

tomato from index $1$ to index $2,$ resulting in the following array.

pots $\{\begin{array}{ccc}\text{:}[1,& 1,& 1]\end{array}$

Now all pots have the same number of tomato$($s$).$ Your objective is to determine the minimum

number of moves needed.

Here's another example scenario to consider.

pots

In this scenario we have $3$ pots but $8$ tomatoes. In this particular example, there is not actual

solution since we cannot evenly distribute the $8$ tomatoes to three pots.

For this assignment, you must follow these requirements.

Create your solution defined in a class called tomatoes.

You will need to implement a method called minTomatomoves. The method is non$-$

static that takes a reference to an integer array $($that is not dynamic$)$ and returns an integer

value that represents the minimum number of moves. Note, the integer array is declared

in the driver file. This array represents the number of pots and each value represents the

number of tomatoes for the respective pot. You will be passing this array to the method.

This method MUST have a theoretical running time of $O(n)$ where $n$ is number of pots.

In other words, the size of the array. This method is called in the provided driver file.

Constructors are not needed for this assignment. You are going to implement the greedy

method only.

You are welcome to create additional helper methods as you see fit. Please make sure that

the methods are implemented in your solution file and NOT the driver file $($as the driver

file will be modified for grading purposes$).$

Your solution must use a Greedy Technique! If a greedy technique is not used, then no

credit will be given for the test cases and method implementation.

You can assume that you can hold multiple tomatoes at a time from a single pot and

move them over to another pot $($which can count as a single move$).$

Each time a set of tomatoes is placed in a pot, a move is counted. Sometimes you may not

have to place all tomatoes in your hand into the pot.

Theoretical Constraint: In this assignment your main method that will compute the solution

must run theoretically in $O(n).$ If your solution does not follow this theoretical constraint, then a

score of $0$ is applied as the grade for the assignment with no other partial credit from any

components of the rubric.

Time Constraints: For this assignment, your code solution must entirely run within $1$ second on

Eustis. If your solution takes longer than $1$ second, then a score of $0$ will be applied to the

assignment grade with no partial credit. The test script already has timeout exception set so you

can test your code's time constraints. As long as you follow the theoretical constraints, your code

should be able to run fast!