This week's book giveaway is in the Go forum.We're giving away four copies of Head First Go and have Jay McGavren on-line!See this thread for details.
Win a copy of Head First Go this week in the Go forum!
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
• Campbell Ritchie
• Liutauras Vilda
• Bear Bibeault
• Paul Clapham
• Jeanne Boyarsky
Sheriffs:
• Devaka Cooray
• Junilu Lacar
• Tim Cooke
Saloon Keepers:
• Tim Moores
• Ron McLeod
• Tim Holloway
• Claude Moore
• Stephan van Hulst
Bartenders:
• Winston Gutkowski
• Carey Brown
• Frits Walraven

# Distribute Chocolate evenly among friends

Ranch Hand
Posts: 53
3
Hi!

I am to write a program that will calculate the number of operations needed to distribute chocolate to my friends. The possible Operations are:
Give 1 chocolate piece to every colleague except for the chosen one.
Give 2 chocolate pieces to every colleague except for the chosen one.
Give 5 chocolate pieces to every colleague except for the chosen one.

The input will be
1. line: int n= NumberOfTestcases followed by 2n lines similar to the following:
4
2 2 3 7

4 is the number of friends, 2 2 3 7 is with how many pieces of chocolate they start.

My Code works for small examples but for many People (There are testcases with up to 600 people) it exceeds the time limit of 10 seconds.

My basic idea is that I have to find the lowest number as well as the second lowes number and add to the lowest until it equals the second lowest. Then again find the second lowest and repeat.
What is slowing my code down ? What can I do to make it faster? Is there a more efficient approach to this that I am missing?
The following is my Code:

Louis

Bartender
Posts: 5652
56
• 1
To significantly improve performance usually means re-thinking the algorithm that you chose. I can't quite make out the goal given the description you posted. Can you give us more details?

Ranch Hand
Posts: 277
2
If its too slow then the amount of iterations of the data is too many.  You can see that your code iterates through thr data many times because you have alot of for loops.

Try to loop through the data and do the work as few times as possible

Louis Müller
Ranch Hand
Posts: 53
3
This is the task I'm trying to solve:

One of the program managers gets to know this and orders Daenerys to ensure that everyone has the same amount of chocolate pieces.

But to make things difficult, she is ordered to even out the number of chocolate pieces for every colleague in the following manner.

For every operation, she can choose one of her colleagues and do one of the following 3 things:

She can give 1 chocolate piece to every colleague except for the chosen one.
She can give 2 chocolate pieces to every colleague except for the chosen one.
She can give 5 chocolate pieces to every colleague except for the chosen one.
Calculate the minimum number of such operations needed to ensure that every colleague has the same amount of chocolate pieces.

Input Specification
First line contains an integer T denoting the number of testcases. T testcases then follow.

Each testcase has 2 lines. First line of each testcase contains an integer N denoting the number of colleagues, second line contains N space separated integers denoting the amount of chocolate pieces that each colleague currently has.

Output Specification
T lines, each containing the minimum number of operations needed to ensure that all colleagues have the same amount of chocolate pieces.

Sample Input
1
4
2 2 3 7
Sample Output
2

Explanation: 1st operation - Daenerys increases all elements by 1 except for the third one 2 2 3 7 -> 3 3 3 8; 2nd operation - Daenerys increases all elements by 5 except for the last one 3 3 3 8 -> 8 8 8 8.

Al Hobbs
Ranch Hand
Posts: 277
2
In the get smallestanddelta it looks like youre getting the second smallest amount of chocolate and the difference between the least and second least amount.   Maybe im reading it wrong but you could possibly get those values in one loop if you have two references.  One for the smallest value and one for the previous smallest value.

Al Hobbs
Ranch Hand
Posts: 277
2
For that one thing i said to work you need to sort them so  they are descending. I think.....

Al Hobbs
Ranch Hand
Posts: 277
2
• 1
Ok i got it now.   You can actually do one iteration of the list and get the answer.  Way faster right?

First you sort in descending order
Then you iterate adding the deltas to a list.
Then iterate through that delta list calculating how many additions you need per delta and then add that delta to the next delta in the list.
Boom baby thats like less than 2n
Maybe i wrong i havent tested it but maybe i will

Al Hobbs
Ranch Hand
Posts: 277
2
• 1
I tested it and it worked so it will pass if you do it like I said.  The way you wrote it, it runs in quadratic time i think. So if you have 600 people, it will look at the numbers 360,000 if they are all different as opposed to 600.

Actually, if it's sorted you can get the count in one iteration if its ascending and you calculate the deltas and count while you iterate through them.

Al Hobbs
Ranch Hand
Posts: 277
2
Actually, since your code iterates the list 2 times in the smallestMethod and then one more time when it adds the numbers, if there are 600 people and they have different amount of chocolate it will iterate through the list 1800 times.  Which is a big difference compared to 1 time

Marshal
Posts: 63489
207
• 1
But all those numbers still count as linear complexity; if you change to 300 people it will take approximately 50% of the time to execute. You cannot sort a List in linear time; since the faster sorting algorithms run in nlogn time, that will make the whole program run in nlogn time.
Some sorting algorithms can run in linear time under certain special circumstances, e.g. Timsort.

Al Hobbs
Ranch Hand
Posts: 277
2
I agree the 1800 vs 600 doesn't differ in complexity I was just saying it because it's sounds more extreme   .   I wasn't counting the sort in my calculation so that's why I said linear. logarithmic time is still good though. sorry if my words were misleading.

Marshal
Posts: 6595
443
• 1

Al Hobbs wrote:logarithmic time is still good though

Logarithmic (O(logn)) time complexity is better than linear (O(n)). What Campbell mentioned about the sorting algorithms, that most some of them can achieve nlogn at best.

But I think you just misspelled and actually got in your mind correctly

Louis Müller
Ranch Hand
Posts: 53
3

I still get wrong answer in 2/3 testcases. But its propably 100 times faster now : D Thank you so far. Any ideas why it doesnt work properly for the bigger numbers?

Louis Müller
Ranch Hand
Posts: 53
3

Liutauras Vilda wrote:

Al Hobbs wrote:logarithmic time is still good though

Logarithmic (O(logn)) time complexity is better than linear (O(n)). What Campbell mentioned about the sorting algorithms, that most some of them can achieve nlogn at best.

But I think you just misspelled and actually got in your mind correctly

So glad you said this. I was utterly confused. I dont know a lot about algorithms but I was sure logarithmic would be the faster one. Just from what I know about linear functions and logarithmic functions : D

Al Hobbs
Ranch Hand
Posts: 277
2

Liutauras Vilda wrote:
Logarithmic (O(logn)) time complexity is better than linear (O(n)).

Sorry I meant linearithmic

Al Hobbs
Ranch Hand
Posts: 277
2

Louis Müller wrote:I still get wrong answer in 2/3 testcases.

Are you getting it wrong because it's taking to long or the answers are just wrong?

Al Hobbs
Ranch Hand
Posts: 277
2
• 1
If you are getting it wrong it might be because you are including deltas equal to 0 in your deltaList.  For example, if the deltas are 1 0 4 , it won't skip over the 0 because the 0 becomes a 1.

Liutauras Vilda
Marshal
Posts: 6595
443
• 1

Louis Müller wrote:So glad you said this. I was utterly confused. I dont know a lot about algorithms but I was sure logarithmic would be the faster one. Just from what I know about linear functions and logarithmic functions : D

Always helps to understand some mechanics. For example:

If you have a linear algorithm, to find out whether the number 8 is in the list of given numbers can take up to 8 (including) steps, depending where this number resides if at all:
[1, 2, 3, 4, 5, 6, 7, 8]
In this case it would take 8 steps, because number 8 is the last in the given list of numbers. That is said linear, because you go through each of element and checking whether it is the number you are looking for or not. So the number of check operations increases equally to the increase of input size.

The logarithmic example would be the binary search tree, it is a data structure, which employs algorithms which can find a number in logarithmic time (can be worse, research in which scenarios). An example:

Now, to find whether the number 8 is among the given numbers would take at most 3 operations. You have noticed, that 4 is the root element, and all the numbers to the left are smaller than 4, and all the numbers to the right of 4 are larger. So you check whether the number 8 is larger than the root number (4), which is, then you know your number could be only in the right branch. So again, you check whether your searchable number is smaller or greater than 7, which is greater again, so could be only on the right hand side, then you check whether the number 8 is smaller or greater, no, it is equal this time, so 3rd operation done and you figured out, that number 8 is among the numbers.

That is essentially what Log 8 is equal to, 3. Log is of base 2, that means, Log 8 is how calculated? To which power you need to raise 2 in order to get 8? 2 to the power of 2 is 4, 2 to the power of 3 is 8. 2 x 2 x 2 = 8.

So if you are given 64 elements, in linear fashion to find the number could take up to 64 operations (again, if number appears to be the last one), in case of logarithmic algorithm, it would take 6 steps at most (given correct data structure and algorithm). Log 64 is 6 (2 x 2 x 2 x 2 x 2 x 2 = 64).

See the difference how the amount of operations increases in case of Linear and Logarithmic algorithms when the input grows?

All that is slightly out of discussion, but hope it will help you to research this topic further. There is a lot in it, some of the parts are easier to understand than others. But that is an essential topic in computer science and you need to understand it to some extent. Never ending learning process.

Louis Müller
Ranch Hand
Posts: 53
3

Added the simpel if(delta!=0) condition nbut still 2/3 testcases wrong answer. Its taking aroun 0.5 seconds to run so timing is not an option anymore you really helped me with that.

Liutauras Vilda
Marshal
Posts: 6595
443
• 1
Try to decompose method to many smaller methods. Currently as it is, it is hard to follow as it does more than one thing, hence harder to spot where your logic flaws. Name methods clearly so they explain exactly their purpose, that way for the bugs will be much harder to slip in.

Liutauras Vilda
Marshal
Posts: 6595
443
• 1

Collections.sort(relevantList);

Line 4. This method invocation has side-effect. It modifies the list passed as an argument (at a caller level). Whether it is desired effect or not - for you to decide.

Louis Müller
Ranch Hand
Posts: 53
3

If you are getting it wrong it might be because you are including deltas equal to 0 in your deltaList.  For example, if the deltas are 1 0 4 , it won't skip over the 0 because the 0 becomes a 1.

I am now convinced that it is neccessary to include the 0's.
Because the operations are based on giving everyone but one person chocolate, not based on giving everyone but "all the persons with specific amount" nothing.
Take for example:
5 people
2 2 3 3 8 pieces
first delta is 0 -> no operation
2nd delta is 1 --> one operation but this operation also increases the delta of the second person with 3 chocolate pieces.
So in this example the correct answer is 4 operations ( +1 , +1, +5, +1)

My new and hopefully more readable code:

Louis Müller
Ranch Hand
Posts: 53
3

Line 4. This method invocation has side-effect. It modifies the list passed as an argument (at a caller level). Whether it is desired effect or not - for you to decide.

hm I thought about this but I think that is not a problem, in fact it's actually what I need. Because I have to start adding pieces to the guys with the smalles amount of chocolate to fill the gaps.
Actually now that Im writing this Im not entirely sure whether it might work from the other side too. I have to rethink this.

Al Hobbs
Ranch Hand
Posts: 277
2
Omg i had it wrong the whole time.  The algorithm might not even work lol

Liutauras Vilda
Marshal
Posts: 6595
443
I just had a look now to the problem description.

So my personal suggestion would be to stop writing code and go back to paper. Basically what Carey mentioned about re-thinking an algorithm.

@OP

Can you describe in English what your algorithm is?

Louis Müller
Ranch Hand
Posts: 53
3
I rethink my algorithm when I come back. For now here is my description of my current algorithm.

First I line up all the participants in a row in ascending order from left to right. I check  the difference in chocolate pieces between the first and the second, the second and the third and so on. I write down all the differences. Next I start with the first guy who has more chocolate pieces than the guys who have the least and I give everyone but this guy as many chocolate pieces as needed so that He and the guys with the least chocolate pieces are even. This means I added this guy to the group of people with the least amount of chocolate pieces. I proceed to do this until I have reached the last guy in the row and all of them are even. Because everyone standing left and right from the guy who gets no pieces gets the same amount of chocolate pieces, i have to update my list of differences. But I dont have to update them all since it is about the difference in chocolate pieces and not about how many they actually have. And since all of them get the same amount of pieces, only the difference between my current guy and the guy on is right is rising.

Thats about it iI think it should work but I will rethink it after training this evening!

Louis Müller
Ranch Hand
Posts: 53
3
• 1
I figured it out. As usual it was a small and stupid mistake. Actually two of them. In line 38-40 you can see that i 1. didnt include the case of delta =2 in my condition and 2. divided by 5 and %ed by 5. This was no problem for the smaller test case but as soon as cases with 5> delta >=2 emerged it was bound to fail. I have to make it a habbit to really check the small things. To save time i just copied the code of the if condition. This lead to a loss of at least 4 hours changing various parts of my code : D
Thanks for all of your help and see you next time!

Carey Brown
Bartender
Posts: 5652
56
• 1
Congrats!