- Practice
- Algorithms
- Dynamic Programming
- Equal
- Discussions

# Equal

# Equal

namdx1987 + 30 comments I think we don't need to use dynamic programming here. First of all, if you give chocolate bars to all but chosen one, it is equivalent to take away the chocolate bar(s) from each chosen one until every one is equal. So the challenge becomes decrease from each individual 1, 2 or 5 until all are equal. Second to calculate the ops we need to use to decrease an integer n until it reaches 0 (call it the function f) is equivalent to convert 1, 5 (no need to use dynamic programming here). Finally, to solve this challenge, we find the min (call it m) of the given list, then for i from 0 to 4, we find min of ops[i]=sum(f(c-min+i)) where c is each individual colleague and thus no need to use dynamic programming here :)

dinu_94 + 1 comment hey namdx, could you explain the concept of how giving chocolate bars to all but one is equivalent to taking chocolate bar from 1 only.

decuqa + 1 comment You have to focus on the difference. If every other colleagues receive a chocolate (because you have the greatest number of chocolates) the difference between your number of chocolates and the colleagues number will decrease.

singhavdeshk + 3 comments @decuqa I have understood how the reduction will work. But i am unable to realise the same answer using the increment algo. For ex: 2 5 5 5 5 5, the operation count would be 6 as we reduce it to 0. But how in just 6 operations we can achieve this using increment technique which is our real problem statement. So, how exactly they are same in real?

soltree12 + 8 comments (2) 5 5 5 5 5

2 (7) 7 7 7 7

7 7 (12) 12 12 12

12 12 12 (19) 19 19

19 19 19 19 (24) 24

24 24 24 24 24 (29)

29 29 29 29 29 29

It's a same choice.

singhavdeshk + 1 comment Thanks. Got it. But there is an cal error in your operations. Instead of 12 12 12 (19) 19 19, it should be 12 12 12 (17) 17 17. Therefore, finally it would be 27 27 27 27 27 27.

zabed_akbar + 4 comments Possible in 5 step.

- 2 (5) 5 5 5 5
- 5 5 (8) 8 8 8
- 8 8 8 (11) 11 11
- 11 11 11 11 (14) 14
- 14 14 14 14 14 (17)
- 17 17 17 17 17 17

Dipak_Prajapati + 2 comments You Miss this condition

**you give chocolate bars to all but chosen one.**so you wont able to give chocolates to all at once.shivanshsahu753 + 0 comments [deleted]augburto + 0 comments They should really bold this in the question. I didn't realize this making the problem seem very hard for me.

Dazzler__ + 0 comments In second step, U have added 3, but addition of 1, 2 and 5 is ony possible

himharsh1997 + 0 comments logic is about making equal not zero.So in 2 5 5 5 5 5.If we reduce 3 from all 5 we left with each having 2 chocolate and that's what we want equal chocolates.

harryapotter + 1 comment 12 12 12 (19) 19 19 19 19 19 19 (24) 24 ???

udaygupta888 + 0 comments we can end it at 13 13 13 13 13 13 also but operations required are 6 only.

edemohankrishna1 + 7 comments Thanks.But I got some other method which would solve by 4 operations please suggest any loop holes in my metghod. step 1:place the values in the list step 2:[1,3,5] are the possible ways to give chocolates step 3: calculate minimum_of_list and maximum_of_list and index where maximum_of_list is present in list(if we have multiple maximum_of_list it has to return first_index) step 4:diff = maximum_of_list - minimum_of_list step 5:add the diff to all the list elements except to maximum_of_list step 6:repeat step 3 to step 5 until all the values are equal in alist Example: (x):assume x is a small value [x]:assume x is maximum_of_list 2 5 5 5 5 (2) [5] 5 5 5 (5) 5 [8] 8 8 (8) 8 8 [11] 11 (11) 11 11 11 [14] 14 14 14 14 14

malawatharshil + 0 comments Have you implemented this approach??

lavanshu_seth + 1 comment the ways to give choclates is {1,2,5} and not {1,3,5}

todd24 + 1 comment That's not what the problem states.

lavanshu_seth + 0 comments I guess you figured out that statement has changed since. It was {1,2,5} two months ago

tyagisagar79 + 1 comment You cannot add 3 to any number. # will be added as combination of 1 and 2 which leads to 2 operation. Eveny my approach was same but got it wrong.

aji011992 + 0 comments Could you please tell me how to solve 1 2 3 4 5 6

todd24 + 4 comments somebody changed the problem to [1,3,5] from [1,2,5] but didn't change the solutions

mister_x + 0 comments Yup.

patkovskyi + 0 comments Spent a few hours debugging my solution before going to forum in desperation and reading this comment...

eloyekunle + 0 comments Has this been resolved now?

aravindhsr001 + 0 comments if the difference is other than 1,2,5 how will you proceed next??

mudassir_fazal + 0 comments This would have slow performance.

NueTron_Star + 0 comments It doesn't give optimal solution in all cases. TC => 2 5 5 5 5 5 expected=> 6 actual=>10

I implemented it so I know. The problem occurs because we are always adding to lower elements which causes problems as it is not proved to be safe move.

Also it give TLE.

manish626kapil + 1 comment [deleted]malawatharshil + 1 comment yup according to

edemohankrishna1JitindraFartiyal + 0 comments Shouldn't be 3 2 3 5 7 1) 7 8 10 (7) 2) 10 11 (10) 10 3) 11 (11) 11 11

aji011992 + 0 comments How did you decide you need to add 2 for the first iteration and 5 for the second iteration ?

orgilthechaser + 1 comment (2) 5 5 5 5 5 (5) 5 8 8 8 8 (8) 8 8 11 11 11 (11) 11 11 11 14 14 (14) 14 14 14 14 17 (17) 17 17 17 17 17

only 5 steps

JitindraFartiyal + 0 comments Yeah, with the differene method, 5 is coming only. But, in the test case it is saying 6 steps

anuragkedia_21 + 0 comments @singhavdeshk for 2 5 5 5 5 5 operartion count will not be 6 it will be 5 2 5 5 5 5 5 5 5 8 8 8 8 8 8 8 11 11 11 11 11 11 11 14 14 14 14 14 14 14 17 17 17 17 17 17 17

mayukh111 + 0 comments I've done the same thing that you have shown over here. But, for, say, 1 5 5, By this method, we get: (1) 5 5 (+ 0 steps) 1(5) 5 (+0 steps) 5 5 (9) (+2 steps) 9 9 9 (+2 steps) = 4 steps. However, in some other manner: (1) 5 5 (+0 steps) 1 (5) 5 (+0 steps) 6 5 (10) (+1 steps) sort() (5) 6 10 (+0 steps) 5 (6) 10 (+0 steps) 6 6 (11) (+1 steps) 11 11 11 (+1 steps) = 3 steps

The actual answer for 1,5,5 is 3 but i get 4. Please shed a light on this, im still confused

byungwoo + 3 comments This case operation count : 5

2 (5) 5 5 5 7 5 (10) 10 10 12 10 10 (15) 15 (17) 15 15 15 20 17 17 17 17 (22) 22 22 22 22 22

Please let me know if I am doing something wrong..

hmutiso + 2 comments you are correct; for the input [2, 5, 5, 5, 5], a minimum of 5 operations will suffice.

However, @singhavdeshk enquired about a different input [2, 5, 5, 5, 5, 5], which requires a minimum of 6 operations.

sujairamprasathc + 0 comments [deleted]pandeysdr16 + 0 comments how we are chosing the number , can someone please explain ?

Abhishek2019 + 1 comment you dont need 6 steps in reduction method.

in reduction method reduce all 5 to 2

so it will take 5 steps

and in increment method as @zabed_akbar said only 5 steps required

2 (5) 5 5 5 5

5 5 (8) 8 8 8

8 8 8 (11) 11 11

11 11 11 11 (14) 14

14 14 14 14 14 (17)

17 17 17 17 17 17

washimdas2013 + 0 comments you can't add 3 in your 1st step .....as the problem stated she can give wither 5 or 2 or 1 at once to all but chosen one

decuqa + 3 comments Maybe we can give some details for tricky part: we don't know how many chocolates to give at the beginning to get the mininal path. For example let's take as initial problem "1 2 4" and compute the difference between the minimum colleague (=1) and the others so you start with "0 1 3" :

if you add +5 chocolates, you get "6 7 4" and the difference increases to "2 3 0" => not good!

now add +2 chocolates so you get "3 4 4" and the difference is decrease to "0 1 1" => much better!!!

adding +1 chocolates "2 3 4" and "0 1 2" => intermediate solution.

So the optimal first move is adding +2 chocolates for every colleagues excepted the last one.

Finaly the problem becomes: "reducing the difference between the number of colleague chocolates".

But if we start immediately to answer this new problem we will have an issue: how to deal with this example : "4 4 3"? In this case it is better to not start the reducing part because the initial state is not optimal. Let's transform it to "4 5 4" and then "5 5 5" and removing -5 chocolates is quicker than removing -2 chocolates with the initial state ("4 4 3"). Five operations < six operations!DWT101092 + 1 comment That's still not really a problem: we only need to get the same amount of chocolate to everyone, not to get to 0 chocolates (when we think about this as subtraction)! In most cases, this just means lowering everyone's total to the min, and thinking about it this way gives the correct answer most of the time (as far as I can tell).

However, we run into some other problems when it would be "better" for us to have a lower min: what if we have 7 7 7 4 4 3? We could lower all of these to 3 in 8 moves (2x -2 for each 7, 1x -1 for each 4), but if we lower everything to 2, then we get fewer moves (1x -5 for each 7, 1x -2 for each 4, 1x -1 for the 3).baran_jana + 3 comments baseline is not necessarily 0. It is a number between the minimum in the sequence M and the max(0, (M - 4)).

the_dark_kai + 1 comment Can you please elaborate why? I can't seem to formalize this

baran_jana + 14 comments The cost to equalize the colleagues is the sum of the reduce operations through all colleagues. Naturally you use as the baseline the minimum colleague and you are taking away from other colleagues until they are equal. However, given you can reduce by 1, 2, or 5, you naturally want to take bigger steps and use as many 5 reductions as possibly and then 2 and only after that reduce by 1.

Now imagine reducing the case 3 7 7. If you would be strictly equalizing them with the miminum colleague then you need to reduce them all to 3 in which case you cannot apply -5 because 7-5=2 is too low hence you need to apply -2 twice. In this case it is cheaper to adjust the minimum to 2. I.e. 377->327->322->222 is cheaper then 377->357->337->335->333.

Now thinking about it again, it is not necessary to calculate for 5 different baselines, 3 is enough: the minimum in the sequence M, M - 1, M - 2 (given M > 2).

In other words reducing by 1 or 2 is cheap (1 operation), by 3 or 4 is expensive (2 operations), 5 is cheap again. By cheaply reducing the basiline by 1 or 2 with a single operation reduction you can save multiple 2 operation reductions on other colleagues.

the_dark_kai + 0 comments Thank you so much for the wonderful explaination

jbowler2400 + 0 comments Very nice. This is one of those problems that once I see it explained well, it makes total sense. But coming to that solution on my own would be the tricky part. I suppose practice makes perfect... I am kind of just getting started with these kinds of problems.

bnegrao + 1 comment I still don't get it. Can someone explain to me how would baran_jana's algorithm work for the problem test case?

`1 4 2 2 3 7`

(it should return '2').

ronaldorocks96 + 1 comment 2237->2227->2222 ( for base line M=2 )

vicky_hacker + 1 comment Can you explain for this case

1 3 1 5 5

dragan_ostojic + 19 comments First find min {1 5 5}. In this case it's 1.

In general, you need to try the following targets: min, min-1, min-2, min-3 and min-4 and target >=0.

So in this particular case min=1 so we try only min and min-1.

Case 1: target is (1 1 1)

Find the delta between (1 5 5) and (1 1 1):

delta = (1 5 5) - (1 1 1) = (0 4 4)

In terms of {1, 2, 5} operations we can minimally partition (0 4 4) elements as follows:

0 = 0 * 5 + 0 * 2 + 0 * 1

4 = 0 * 5 + 2 * 2 + 0 * 1

4 = 0 * 5 + 2 * 2 + 0 * 1

Note that you get above partition as follows:

For some delta = (d0 d1 ... dn-1)

di = ai * 5 + bi * 2 + ci * 1

ai = di / 5

bi = (di % 5) / 2

ci = (((di % 5) % 2) / 1)

Now count the occurences of {1, 2, 5} in (0 4 4) partition and this is the min number of operations to reduce (1 5 5) -> (1 1 1):

min number of ops = (0 + 0 + 0) + (0 + 2 + 0) + (0 + 2 + 0) = 4

Case 2: target is (0 0 0)

Find the delta between (1 5 5) and (0 0 0):

delta = (1 5 5) - (0 0 0) = (1 5 5)

In terms of {1, 2, 5} operations we can minimally partition (1 5 5) elements as follows:

1 = 0 * 5 + 0 * 2 + 1 * 1

5 = 1 * 5 + 0 * 2 + 0 * 1

5 = 1 * 5 + 0 * 2 + 0 * 1

Now count the occurences of {1, 2, 5} in (1 5 5) partition and this is the min number of operations to reduce (1 5 5) -> (0 0 0):

min number of ops = (0 + 0 + 1) + (1 + 0 + 0) + (1 + 0 + 0) = 3

Case 1 requires 4 steps and case 2 requires 3 steps, so case 2 is optimal and min number of steps is 3.

Why do we not look min-5, min-6 etc? Suppose min-5 >=0 so (min-5 min-5 ... min-5) is a valid (non-negative elements) target.

delta' = (v0 - (min -5) ... vn-1 - (min -5)) = (v0 - min + 5 ... vn-1 - min + 5)

When we did (min ... min) target, delta was:

delta = (v0 - min ... vn-1 - min)

Now if you compare partitions of delta and delta' into {1, 2, 5} it's evident that delta' has one more 5 in each element di' so compared to number of ops in delta it requires n extra -5 operations. For that reason each of the cases min-5, min-6 etc are always less optimal than cases min, min-1, ... min-4.

ankurtiwari044 + 1 comment Can you do it in case of

1

3

1 123 834

I dont find a generic algorithm with proof of correctness but everyone is trying to explain seme solution with a trivial example. Please correct me if I am wrong.

dragan_ostojic + 3 comments I'm not clear if you want the solution of the case: 3 coworkers with the following allocation of chocolates:

( 1 3 1123834 )

OR

the case 5 coworkes with the allocation (1 3 1 123 834).

Assume it's the first case. If it's the second just follow below steps closely.

First we find min { 1, 3, 1123834 } = 1. We have two cases and we need to try both and check which has less steps.

Case 1: target = (1 1 1)

delta = (1 3 1123834) - (1 1 1) = (0 2 1123833)

We next find min number of -5, -2 and -1 steps to get from (1 3 1123834) to (1 1 1)

0 = 0 * 5 + 0 * 2 + 0 * 1

2 = 0 * 5 + 1 * 2 + 0 * 1

1123833 = 224766 * 5 + 1 * 2 + 1 * 1

Total # of steps: (# of steps to make 0 -> 1) + (# of steps to make 2 -> 1) + (# of steps to make 1123833 -> 1) = (0 + 0 + 0) + (0 + 1 + 0) + (224766 + 1 + 1) = 224769

Case 2: target = (0 0 0)

delta = (1 3 1123834) - (0 0 0) = (1 3 1123834)

We next find min number of -5, -2 and -1 steps to get from (1 3 1123834) to (0 0 0)

1 = 0 * 5 + 0 * 2 + 1 * 1

3 = 0 * 5 + 1 * 2 + 1 * 1

1123834 = 224766 * 5 + 2 * 2 + 0 * 1

Total # of steps: (# of steps to make 1 -> 0) + (# of steps to make 3 -> 0) + (# of steps to make 1123834 -> 0) = (0 + 0 + 1) + (0 + 1 + 1) + (224766 + 2 + 0) = 224771

We see that case 1 requires fewer steps so min number of steps is 224769.

Twinkle_twinkles + 0 comments Thanku very much....ur explanation is very helpful to solve this problem efficiently..:)

donotevermailve1 + 0 comments could you explain for 1 123 834 please

demure + 0 comments if u consider the case of 1 4 1123834. You need to consider (-1,-1,-1) as well to get the ans.

case 1:(1,4,1123834)->(1,1,1)=(0,3,1123833) steps (0,2,224768), Total = 224770

case 2:(1,4,1123834)->(0,0,0)=(1,4,1123834) steps (1,2,224768) Total = 224771

case 2:(1,4,1123834)->(-1,-1,-1)=(2,5,1123835) steps (1,1,224767) Total = 224769

ans = min(224770,224771,224769) = 224769.

anilkaliya_au + 1 comment [deleted]anilkaliya_au + 0 comments [deleted]

rjulius23 + 0 comments thanks. it is like i got it with baran_jana but i finally got it 100% with your example... i guess i needed a practical explanation :)

lit_player + 1 comment your solution is great, but I don't get the di=ai*5+bi*2+ci*1 part. what does a,b,c's denote here. what if the problem has more than 3 collegaues.

rjulius23 + 1 comment a is the number of decution by 5 steps, b is the number of deduction by 2 steps, c is the number of deduction by 1 steps

They are nothing to do with the number of colleagues.

You have 3 ways either deduct 5 or 2 or 1.

lit_player + 0 comments got it , thanks a lot. :)

tranmonglong0611 + 0 comments thank you so much

hariharan90000 + 2 comments @dragan_ostojic Why should the baseline be >= 0 ? Why cant we make it -1,-2 ( upto minimum - 4 ) and try to make all the numbers reach -1 or -2?

thefriction + 2 comments @hariharan90000 Had the same doubt seeing the above comments but no one mentioned why and i couldn't find any logic to that arguement.

It can be

There is nothing wrong with our M-x becoming -ive cause in the original question we are adding values to nos. so they can never be negative.It is just to make our compress our question we are subtracting and getting -ive values and so it won't affect the original problem.

Consider the eg:

1 4 4

M=1 if x = 0 M-x = 1 ans = 4

if x = 1 M-x = 0 ans = 4

if x = 2 M-x = -1 ans = 3 ( 1 4 4 1 6 6 6 6 11 11 11 11)

that's lesser than wat we would get for M-x>=0

Plz Correct me if i'm wrong.

architkl + 0 comments I had the same doubt and I think you're right. Considering the 1 4 4 example it should be necessary to take into account a -ve baseline as originally the question was of addition.

rishabh_ags + 0 comments I can confirm that you are correct. for my case if m is min of given list of chocolates, then we gotta check m,m-1,m-2 to find the correct answer.

agordonwright + 0 comments For some cases, my algorithm only worked when I checked targets<0. But maybe it's just my shoddy coding...

Dvjsm + 0 comments [deleted]sabarirangan + 0 comments [deleted]sabarirangan + 0 comments can you share me the proof of correctness of your algorithm in mathematical form

agordonwright + 1 comment I like this explanation. After struggling with this problem for ages, implementing this method (almost) worked. But for input 15 only, my code still got WA about half the time when minimum%5==0, whether minimum==0 or some higher value. Can't work out why... So I ended up considering target=(min...min-4) for all inputs, which is slower but worked. I am not sure about the reasoning why target must always be >= 0.

tayalaru14 + 1 comment hello, I am also getting WA for test case 15. But even after taking target till (min-4) I am not getting it right. Can U suggest something to debug.

tvhong + 1 comment For me, it was because I skip if baseLine is negative:

for (int k = 0; k < 5; k++) { baseLine = minChocolate - k; if (baseLine < 0) continue; // wrong! // the rest }

shivam_jain + 0 comments It helped.Thanks

samuu + 0 comments @dragan_ostojic you must really be a genius

Lifes_a_code + 0 comments [deleted]Lifes_a_code + 0 comments Your explaination was really helpful in solving this question with just one minor change. I didn't imposed any condition on target and let that loop run from min to min-3 as it would satisfy the case 1 4 4 suggested by someone here by setting target at -1. thank you.

true_idiot + 0 comments Thanks, I was stuck in this problem your explanation really helped.

hmutiso + 0 comments @dragan_ostojic, thank you for this explanation, it's clear and easy to follow.

One question: You can use the same argument used to eliminate (min-5) as a viable target to also eliminate (min-3) and (min-4). Stated differently:

Let (min-3) >= 0 such that [min-3 min-3 ... min-3] is a valid non-negative target.

delta'' = [v0 - (min-3) ... vn-1 - (min-3)] = [v0 - min + 3 ... vn-1 - min + 3]

Compared to our original target of [min ... min], and

delta = [v0-min ... vn-1 - min],

it's clear that delta'' results in 2n more operations than delta. Therefore, we should not need to consider (min-3).

Similarly, we shouldn't need to consider (min-4), because

delta''' = [v0 - min + 4 ... vn-1 - min + 4] results in 2n more operations than

delta = [v0-min ... vn-1 - min].

So my question: Isn't it sufficient to check ONLY for (min), (min-1) and (min-2)?

pareek_kunal83 + 0 comments [deleted]chumaagogbua + 0 comments @dragan_ostojic thank you for the explanation. Its amazingly clear and efficient. I just want to add that

**target >= 0**does not work for all cases. When the condition allows**target**to be**-ve**or**+ve**it works for all test casespandeysdr16 + 0 comments Hi , Can you please explain how did you come up with this formula ?

For some delta = (d0 d1 ... dn-1)

di = ai * 5 + bi * 2 + ci * 1

ai = di / 5

bi = (di % 5) / 2

ci = (((di % 5) % 2) / 1)

benedict_ + 0 comments how did you got the values of ai,bi,ci?? Is there a method to solve that equation which i don't know ??

ronaldorocks96 + 0 comments That was amazing explanation.

neonwave + 1 comment I am having problem with test case#11. @baran_jana can you explain it for 1 5 5

dragan_ostojic + 0 comments Take a look into explanation I provided above: https://www.hackerrank.com/challenges/equal/forum/comments/227783

chandra_thumulu1 + 1 comment @baran_jana, In the above example, 377 is reduced to 333 using 2 operations, that is, 377 -> 355 and 355 -> 333. But I didn't follow how it is reduced to 222. In one operation if you are using 5 to reduce, then 377 -> 322. But how did 322 become 222? Can you please explain a bit?

dragan_ostojic + 1 comment To reduce to 222 is to decompose (377) - (222) = (155)

1 = 0*5 + 0*2 + 1*1

5 = 1*5 + 0*2 + 0*1

5 = 1*5 + 0*2 + 0*1

We see that reduction consist of one -1 followed by 2 -5:

377->277->227->222

Total of 3 operations

To be clear you can reduce by ONE operation at a time.

chandra_thumulu1 + 1 comment @dragan_ostojic, thanks for your response. when we reduce 377 by 1, we need to choose one of the interns, and reduce every other by 1. This means, 377 should become 267 or 366. how did it become 277?

dragan_ostojic + 2 comments no, it's not how it works. if you reduce, you choose only ONE at a time. if you increase you choose all EXCEPT the one you chose when you reduce. these two problems are equivalent i.e. if you solve reduction problem you also solved addition problem. note that the problem as originally stated is addition. the reason we choose reduction approach is because it's simpler. let me demonstrate first reduction solution and then how you derive addition solution from it.

Reduction:

3 7 7->2 7 7->2 2 7->2 2 2

steps:

dec 1st by 1

dec 2nd by 5

dec 3rd by 5

Addition:

3 7 7->3 8 8->8 8 13->13 13 13

steps:

inc all BUT 1st by 1

inc all BUT 2nd by 5

inc all BUT 3rd by 5

This is how Christy the intern is required to solve it. But she will first pretend that she was asked to solve it by taking away one at a time. Once she did that she would know how to solve by adding chocolates.

Look at my response to an earlier question, I explained in detail how you exactly find the solution for any reduction problem. Once you know the steps for reduction problem you can easily derive the steps for the equivalent addition problem as required.

chandra_thumulu1 + 1 comment @dragan_ostojic okay. can you also post the link to your response to the other question?

dragan_ostojic + 1 comment chandra_thumulu1 + 0 comments Oh, its for the same problem. Thanks for sharing it. I'll go through it and get back to you in case I've any followup questions. Thanks!

ntextreme3 + 0 comments awesome explanation, thanks !

louisluhao + 0 comments Thank you for such a clear explaination. I was so close to this. I was thinking about M, M - 1, M - 2, M - 5.

bazuka_ + 1 comment what is the output for the test case

1 3 1 5 5

my answer is 4 but correct output showing is 3 can someone explain me the reason for this test case?

karthsai + 1 comment The optimal solution for 1 5 5 is as follows: 1- 1+5,5,5+5 -- 6,5,10 2- 6+5,5+5,10 -- 11,10,10 3- 11,10+1,10+1 -- 11,11,11

So that could be done in 3 steps.

nitinbansal53 + 0 comments This is the explanation i was looking for this test case. Thanks!

saurav_agarwal21 + 0 comments Hey, Baran Jana! I am getting some segmentation fault while using your logic. I am only checking for M,M-1 and M-2. Is there something else where I might be going wrong?

jindalshubham34 + 0 comments That was the theory what would be the algo

Abhishek2019 + 0 comments can u give answer for : 1 4 1 5 5 5

prashank_jauhari + 0 comments I under stand your approch. It is greedy. But Why this question is marked as DP? Thing thing is really creating confusion.

shritej24c + 0 comments do it for [3,7,7,7]

sanjose_coder + 0 comments Hi baran_jana, if the minimum value in the initial array is 0, your algorithm does not work. What to do for baseline 0 case?

rahulrj25 + 1 comment By using your condition of max(0,(M-4)) last test case fails. I think we must run code fore M to M-4 irrespective of whether it is >=0.

faraday_anshul + 1 comment Yeah you said that right! Got ac with that! I wrote that >=0 condition and got wa in #13th case, But why this is happening? How can chocolates balance in negative lol!

rahulrj25 + 1 comment I think answer is possible because real operations is giving choclates and making them equal and not make equal by removing. So we must just be concered with making them equal as we are removing choclates and making equal, answer will be correct even if we make it negative.

faraday_anshul + 0 comments Yeah you are right!

jiaxianglong1987 + 0 comments So true it hurts

rwan7727 + 1 comment Passed all tests:

int main() { int t; cin >> t; while (t--) { int n; cin >> n; vector <int> a(n); for (int i=0;i<n;i++) cin >> a[i]; // giving x chocs to every colleague other than chosen one // is the same as taking away x chocs from the chosen one int min=*min_element(a.begin(),a.end()); int numops=0; // consider taking away 5 chocs first (nChocs) for (int i=0;i<n;i++) { int nChocs=floor((a[i]-min)/5.0); a[i]-=(5*floor((a[i]-min)/5.0)); numops+=nChocs; } min=*min_element(a.begin(),a.end()); // min of leftovers in a[] // fine tuning for last calc, get freq of diff first vector <int> freq(5); // stores diff of 0 to 4 for (int i=0;i<n;i++) freq[a[i]-min]++; // case of min num of chocs is min int extra_numops=1*(freq[1]+freq[2])+2*(freq[3]+freq[4]); // case of min num of chocs is min-1 int extra_numops1=1*(freq[0]+freq[1]+freq[4])+ 2*(freq[2]+freq[3]); if (extra_numops1<extra_numops) extra_numops=extra_numops1; // case of min num of chocs is min-2 int extra_numops2=1*(freq[0]+freq[3])+ 2*(freq[1]+freq[2]+freq[4]); if (extra_numops2<extra_numops) extra_numops=extra_numops2; cout << numops+extra_numops << endl; } return 0; }

fergus_a_hewson + 1 comment Thanks for the solution :) :) I like the use of the freq table. Are able to offer an explanation of the last few lines?

It appears you getting the min of the operatins for the cases of min, min-1 and min-2. Why not min-3 and min -4?

Thanks in advance :).

rwan7727 + 1 comment They are redundant cause they will never be smaller than the case of min.

fergus_a_hewson + 0 comments I actually saw an explanation under another comment explaining this. It has something to do with; when to reduce 3/4 to zero it can be cheaper to do it via -5 (-1|-2) and reducing the and then others by 2|1.

Reducing 6 9 9 Option 1 (4 moves) -2@1 6 7 9 -2@2 6 7 7

-1@1 6 6 7 -1@2 6 6 6Option 2 (3 moves) 6 9 9 -5@1 6 4 9 -5@2 6 4 4 -2@0 4 4 4

Reducing by 5 first is faster :).

supragya_23 + 0 comments 4 4 3; 7 4 6; 7 7 9; 8 8 9; 9 9 9

doobdoub101 + 0 comments I actually made the very same reasonning and I have a code in O(n). I think they proposed to solve things using DP to voluntarily disturb the programmer. I am getting addicted to this website.

tangtianjie + 1 comment Thanks for your explanation!

Khwarizm + 0 comments [deleted]

harshaldjain1 + 1 comment Thanks. The solution worked for me but my code is getting timed out for certain test cases. The complexity is O(N^2). Any suggestions? Link - https://www.hackerrank.com/challenges/equal/submissions/code/19605416

v4vibhor + 0 comments Make [][] diff of size [n] [4] rather than [n][n].

Khwarizm + 0 comments [deleted]neverloseks + 0 comments so muuuuuuuch appreciate for your help

Oleksandra28 + 1 comment How come "giving chocolate bars to all but chosen one" is equivalent "taking away the chocolate bar(s) from each chosen one until every one is equal"?

chandra_thumulu1 + 0 comments @Oleksandra28 I too didn't get that when I started the solution. But then it made sense after following the discussions here..

Think of this scenario. There are three inters with the chocolate count as follows: 5, 3, 3. In this case you can choose the intern with 5 chocolates and add 2 chocolates to other interns to make the chocolate count 5, 5, 5 or you can choose the intern with 5 chocolates and take 2 chocolates from him to make the chocolate count 3, 3, 3. Both require 1 operation. Does this make sense?

ZhassanB + 1 comment This question can be tagged dynamic programming. Because in the main solution part, we memorize the differences. The nutshell of dynamic programming is memorization. It is clear from this slice of code from my solution:

static final delta[] = {0,1,2,5}; private static int solve(int a[]){ Arrays.sort(a); int res = Integer.MAX_VALUE; for(int j = 0;j<delta.length;j++){ int ans = 0; int d = 0; a[0]-=delta[j]; for(int i = 1;i<a.length;i++){ int diff = a[i]-a[i-1]; // refer to prev elements ans+=getMinSteps(diff+d); d+=diff; // memorizing diffs } a[0]+=delta[j]; res = Math.min(res, ans+(delta[j] == 0?0:1)); } return res; }

shanur_cse_nitap + 0 comments its memoization

rmeghwal + 1 comment Hi, I also used the same, but I am unable to findout correct solution if input is 1 5 5 10 10.

After first step(value-min) : 0, 4, 4, 9, 9

step required to make all zero = 0+2+2+3+3=10

but if we try to do in this way like

`0, -1(4-5),-1(4-5),-1(9-2*5), -1(9-2*5) => total steps= 0+1+1+2+2; -1, -1, -1, -1, -1 => total step = 1+0+0+0+0 = 1 So total operation is 7.`

Please let me know if I am doing something worng/incorrect.

ZhassanB + 1 comment Hi rmeghwal! If you are talking to me (it is not obvious from the comments arrangement), then I would like to point out, that my approach is not about making all zeros, but about making all the same. For that purpose I sort out the array first. After that, you see the following picture:

| | | | | | | | | | | |

The figure above is the visualization of numbers sorted in increasing order. After that you have to choose a pivot and increase the rest by either {1,2,5}, and repeat it utill all the numbers are the same. Intuitive step is to put pivot on greater number and adapt the smaller numbers to it and so on. Thus, we traverse the array, and at each iteration we choose current number as pivot, then adapt the prefix array to it. The total number of steps is the sum of steps required in each iteration. But sometimes encreasing the suffix array by either {1,2,5} can give the best result, due to discreteness of the steps. Therefore we need to select the minimum result among all options. You can check that out by yourself for correctness. If you still think that you are doing the same, please show me your code.

geekrittr + 1 comment Hi Zhassan, can you please look into my code and say where i am doing wrong (apart from time complexity),

t1 = 1 t3 = 3 t5 = 5 for _ in range(int(input().strip())): l = int(input().strip()) c = [int(f) for f in input().strip().split(' ')] e = 0 count = 0 while(max(c)!=min(c)): count += 1 mi = min(c) mx = max(c) d = mx-mi if d >= t1 and d < t3: e = t1 elif d >= t3 and d < t5: e = t3 elif d >= t5: e = t5 for i in range(len(c)): if c[i] != mx: c[i]+=e print(count) #print(c)

my answer - 933 expected - 10605 but still all are having same numbers of chocolates.

justinli791 + 1 comment regarding f(c-min+i), why i?

scorpion_ajay + 0 comments rather it can be written as f(c-(min-i)), now it might be clear to you why

mjarun777 + 0 comments i feel the approach of namdx is correct. for the first problem given with values 2 2 3 7 we can get the reach to the final result by taking away the value from one instead of adding to others. here if we remove 1 from 3 the set becomes 2 2 2 7 and then remove 5 from 7 we get 2 2 2 2 hence the final result remain same 2

bazuka_ + 2 comments please help me someone. why for input .

1 3 1 5 5 output is 3 but ans should be 4 as 1- 1+2,5,5+2 -- 3,5,7 2- 3+2,5,7+2 -- 5,5,9 3- 5+2,5+2,9 -- 7,7,9 4- 7+2,7+2,9 -- 9,9,9 ans is 4

singhavdeshk + 1 comment As others have also explained very well. It would be easy if we do it other way that is using Reduction. Min(Elements) is 1. So min-1 and min-0 are 1 and 0. Considering two cases: i) Reducing it to 1: 1 --> 1 = 0 oper, 5 --> 1 = 2 oper and 5 --> 1 = 2 oper. Hence total 4 operations are required. ii) Reducing it to 0: 1 --> 0 = 1 oper, 5 --> 0 = 1 oper and 5 --> 0 = 1 oper. total 3 operations are required.

Therefore min(4,3) we choose reducing it to 0 instead of 1. So answer is 3.

By the way, if you do it by Increasing, still 3 operations required, just follow this: 1- 1,5+1,5+1 -- 1,6,6 2- 1+5,6,6+5 -- 6,6,11 3- 6+5,6+5,11 -- 11,11,11

bazuka_ + 0 comments Thank you i got it..

namanbansal013 + 0 comments 1 (5) 5 ->adding 5

6 5 (10) ->adding 5

(11) 10 10 ->adding 1

11 11 11The answer is 3 only.

Kevinagin + 1 comment **How many steps would it take to decrease 900 chocolates down to 0?**This is the step where the problem authors expect you to use Dynamic Programming. It looks to me like @namdx1987 is suggesting a greedy approach instead, which works perfectly for the "decrease" amounts of 1,2,5.

But there are other decrease amounts for which a greedy approach would not work (such as 1,3,4). So just a slight tweak to this problem would make Dynamic Programming necessary.

Since it's filed under "Dynamic Programming", the problem might be better off with a slight change to the "decrease" amounts. Regardless, I still really like this problem, and I think it's a neat twist off the classic change-making problem.

vijay_rajan + 0 comments I disagree, I still think it will be greedy.

Take the minimization of the problem where you decrement from one person from your set of {1,3,4} instead of adding to all but one {1,3,4}. I see no Dynamic Programming.

Can you list out 1. principal of optimality 2. optimal recursive substructure 3. recurring sub problems?

AnonymousNovice + 0 comments Thank you.

sandhujaikirat + 0 comments I really liked your approach. But can you please give away less. This comment is basically an editorial.

vg_vaibhav96 + 0 comments nice theory and idea

wilmer_henao + 0 comments You're literally describing it as a dynamic programming problem. And claiming that it's not after every sentence.

Rangerix + 1 comment How to select which one to decrement and by which amount(1/2/5)?

manish626kapil + 1 comment [deleted]Rangerix + 1 comment Sorry , but I am unable to understand. Why 4 ? Elaborate , please.

manish626kapil + 0 comments [deleted]

favssama + 0 comments Can you explain why you have to iterate from 0 to 4?

samarendra109 + 1 comment Why 1 ,2 , 5. In qu it's given 1,3,5. Am i missing something??

Neelarghya + 0 comments Miss print, it should be 1, 2 and 5

sayansingha + 0 comments @namdx1987 what is c??thx

rishabhkumartya1 + 0 comments Why are we only reducing 1,2,5 and not 1,3,5 ? Because if we add a 3 in all other but one the effect can be compared to reduction of 3 bars from the chosen person. And after choosing the person for decreement still it is similar to minimum coin (of fixed denomination) question. should we not use Dynamic Programming?

dark_wolf_jss + 0 comments may i know why are you considering 1,2 or 5 where as in the question it is given as 1,3 or 5

dpspar10102 + 1 comment // please tell if there is some minute error, I am getting very very close answers

# include

using namespace std ;

// returns the number of steps needed to make value reach the target int steps(int target,int value) { long steps = 0; long gap = value - target ; if(!gap) return 0;

`steps += gap/5 ; gap = gap % 5 ; steps += gap/3 ; gap = gap% 3; steps += gap/1 ; return steps ;`

}

int main() { int testcases ; cin >> testcases ;

`for(int i=0;i<testcases;i++) { int n ; // number of collegues cin >> n ; int arr[n] ; int min = 9999; for(int i=0;i<n;i++) { int chocs; cin >>chocs ; arr[i] = chocs ; min = (min<chocs)?min:chocs ; // gets the minimum number out of the input elements } // soln[i][j] means steps needed to make elements till i th position reach to min - j . long soln[n][5] ; for(int i=0;i<5;i++) { soln[0][i] = steps(min - i , arr[0]) ; } for(int i=1 ; i<n ;i++) { for(int j=0;j<5;j++) { soln[i][j] = soln[i-1][j] + steps( min - j , arr[i]) ; // may be here is the issue } } long answer = 99999 ; for(int i=0;i<5;i++) { answer = (answer > soln[n-1][i])?soln[n-1][i]:answer ; } cout << answer << "\n" ; }`

}

patkovskyi + 0 comments First of all, change

steps += gap/3 ; gap = gap% 3;

to

steps += gap/2 ; gap = gap%2;

There's been an error in statement/test cases. At some point of time statement said "For each operation, she can give 1,3,5 chocolates to all but one colleague" but test cases were made for "1, 2, 5".

jiaxianglong1987 + 0 comments This is just brilliant. Instead of 'increasing all but one', your idea focuses on 'decreasing one at a time' which makes it much more intuitive. B-e-a-utiful.

NotSoOldNick + 0 comments OK, so this was fairly challenging for me. I first pig-headedly went down the route of adding chocolates to all colleagues but one, and got partially there, but that was real hard and convoluted, and cases 11,12,13, and 15 were still failing. I then went back to this comment and accepted the idea that adding chocolates to all but one was equivalent to removing the same amount of chocolates to one colleague only. Way easier to write and read, but still the same cases were failing. So I read again the end of the comment about getting the minimum value from

**ops[i]=sum(f(c-min+i))**, with i in {0,1,2,3,4}. And the resulting code passed all tests. But for the life of me I cannot figure out why by varying i between 0 and 4 we can get a better output. I'm guessing 4 because 4 is the last integer before 5, but that doesn't cut it. Could someone explain in layman terms why we should run 5 variations to obtain the best result please?tusharyada85 + 0 comments if we have {2,6,6,6} if i use addition approach it will be {(2),7,7,7} {7,(7),12,12} {12,12,12,(17)} {17,17,17,17} and know if i use subtraction approach i.e subtracting one ,two or five from one element at one time it will give me same number of operations . {1,6,6,6} {1,1,6,6} {1,1,1,6} {1,1,1,1} so number of operations are same in both the cases. now you got it

depmeena5 + 0 comments Can you explain how calculating min(op[i]) will give us optimal answer.

muqtadir532 + 0 comments why do we have to iterate i from 0 to 4

lovealmgren + 7 comments **100% correct Java 8 Solution**import java.io.

*; import java.util.*;public class Solution {

`public static long find_min_actions(int[] cookies) { Arrays.sort(cookies); long sum = Long.MAX_VALUE; for(int base = 0; base < 3; base++) { int current_sum = 0; for(int i = 0; i < cookies.length; i++) { int delta = cookies[i] - cookies[0] + base; current_sum += (int)delta / 5 + delta % 5 / 2 + delta % 5 % 2 / 1; } sum = Math.min(current_sum,sum); } return sum; } public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); while(n-->0) { int m = in.nextInt(); int cookies[] = new int[m]; for(int cookie_i=0; cookie_i < m; cookie_i++){ cookies[cookie_i] = in.nextInt(); } System.out.println(find_min_actions(cookies)); } }`

}

Parthasch + 2 comments Thanks for sharing this. Could you please help me in understanding in the below logic. I didnt understand what we are doing here.

for(int base = 0; base < 3; base++) { int current_sum = 0; for(int i = 0; i < cookies.length; i++) { int delta = cookies[i] - cookies[0] + base; current_sum += (int)delta / 5 + delta % 5 / 2 + delta % 5 % 2 / 1; } sum = Math.min(current_sum,sum); }

lovealmgren + 4 comments Hi! First we must realize that adding to all but the chosen one is the same as subtracting from only the chosen one.

Then the other idea is that we must find the optimal solution. For example, 0 4 4 could be solved like this: 0 4 4 --> 0 4 2 --> 0 4 0 --> 0 2 0 --> 0 0 0 -->

But the optimal solution is this: 0 4 4 --> 0 4 -1 --> 0 -1 -1 --> -1 -1 -1 -->

This is what I call the 'base'. and I add it to the delta, and it turns out you have to make at least 3 trials. Hope this helps.

Parthasch + 1 comment Thanks for reply..sorry i coulndt get why we are adding that base to difference between two elements. and then dividing and Module operations. May be i am slow to get all this. Thanks for the reply.

rahul_rowthi + 2 comments Hi Partha, dont make low of your self. Whenever you dont get it take a small example. I will try to help with one.

consider 2,x; The main thing you want to do is make a singleton( or the minimum posssible number of) choice per a candidate. a)If differnce between x and 2 is 5: -adding 0 makes it divisble by 5. (you only made one choice on x). -adding 1 or 2 makes it you to have more number of choices. b)If differnce between x and 2 is 4:

`-adding 1 makes it divisble by 5. (you only made one choice on x). -adding 0 or 2 makes it you to have more number of choices.`

c)If differnce between x and 2 is 3:

-adding 2 makes it divisble by 5. (you only made one choice on x).

-adding 0 or 1 makes it you to have more number of choices.

d)If differnce between x and 2 is 2:

-adding 0 makes it divisble by 2. (you only made one choice on x). -adding 1 or 2 makes it you to have more number of choices. e)If differnce between x and 2 is 1:

-adding 0 makes it divisble by 1. (you only made one choice on x).

-adding 1 or 2 makes it you to have more number of choices.

f)If differnce between x and 2 is 6:

-adding 1 makes it divisble by 5. (you only made two choices on x, first divide by 5 then reminder by divided 2). //same number of choices in this case even by adding 0.

-adding 2 makes it you to have more number of choices.So for every candidate you add some base (0 or 1 0r 2) and consider the only the base that gives you minimum choices.

But why I need add some base?

A basic divisibility exaple. 9 is not perfectly divisible 5 but adding 1 to 9 makes it 10 and now perfectly divisble by 5.

But why base only till 0,1,2 and not more than 2?

if the diffence between x and y is:

a)4 adding 1 is div by 5

b)3 adding 2 is div by 5

c)2 it is div by 2

d)7 is div by 5 followed by 2

e)8 adding 2 is div by 5 followed by 2

f)9 adding 1 is div by 5 followed by 2

Did you observe the base is cycling around 0,1,2.so you never need not go beyond 2Parthasch + 0 comments Thanks for your encouragement and support Rahul. I am slowly getting there.

tusharyadav7 + 0 comments This is a perfect explaination of adding base and finding the best case the logic except base addition would get you clear some test cases by the reducing approach but you would definitely need to add base so that you get the best apporach out of the three possible solutions. Good approach rohit! Thank You

pendell + 1 comment Great stuff here, Lovealmgren. I plan to use a version of this algorithm myself.

Why exactly three bases, no more and no less? Why not two, or four?

If I had to guess, I'd suspect you found out through empirical testing -- add 1 to base in the loop until all test cases pass. That would work -- but is there a more formal mathematical explanation for your solution?

codertoaster + 0 comments [deleted]

Snigdha_Sanat + 0 comments @lovealmgren can u please explain the idea of taking base with only 0,1 and 2?

yaangliu + 0 comments Looks the question is changed from using {5, 2, 1} to {5, 3, 1}, so we might need to change the number value in above code. Otherwise given input {2, 2, 5, 7}, it will give answer 3, but it could be 2. But the test cases are not updated, so this answer will pass all test cases. One more comment, we just need to concern about base in [0: 4], as if base is 5, there will be definitely one more operation needed.

v_y_l + 0 comments Additional comment for clarity. The bases are there because adding to all but the chosen one is

*not completely*the same as subtracting from only the chosen one. (Not until we consider adding the bases 0, 1, 2).For example, to elaborate on the given example, if we had 0 4 4, under the division of (int)delta / 5 + delta % 5 / 2 + delta % 5 % 2 / 1 without bases, we technically cannot account for the option of -5 because we can't apply that to the number delta 4 (or if delta = 3 for that regard). Try running through delta = 4 on your own and you'll see what I mean.

Adding +1 (or +2 for delta = 3) here would fix that problem. We only need bases 0, 1, 2 to account for delta = 3 or 4. Once delta = 2, the superior choice would be to -2 and not -5, so we don't need additional bases.

DandyDan + 1 comment Your solution is O(n*log n) because of sorting. To make it O(n) just find minimum with linear search without sorting.

lovealmgren + 0 comments Yes you are right! Thx

speedy_ss541 + 0 comments Its not showing correct answer

vkgg3 + 0 comments [deleted]malleswarao + 0 comments int delta = cookies[i] - cookies[0] + base; current_sum += (int)delta / 5 + delta % 5 / 2 + delta % 5 % 2 / 1;

hai i am not understanding the delta is the adding element or not.

bhavinjawade + 0 comments My solution is similar to yours but it is not able to pass the last test case... its giving wrong result for a few sets. Can you please help me understand what I did wrong.

import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; public class Main { public static void main(String args[] ) throws Exception { /* Enter your code here. Read input from STDIN. Print output to STDOUT */ Scanner sc = new Scanner(System.in); int t = sc.nextInt(); int n; int q1 = 0,q2 = 0,r1 = 0 ,r2 = 0; int sum = 0; int low; for(int ai = 0 ; ai < t ; ai ++){ n = sc.nextInt(); int[] a = new int[n]; for(int i = 0 ; i < n ; i++){ a[i] = sc.nextInt(); } sum = 0; int k =0; long sum1 = 1000000000; Arrays.sort(a); low = a[0]; for(low = a[0] ; low >= 0 ; low--){ sum = 0; for(int i = 0 ; i < n ; i++){ k = a[i]-low; //System.out.println(low + " " + a[i]); q1 = k/5; r1 = k % 5; q2 = r1/2; r1 = r1 % 2; sum = sum + r1 + q2 + q1; //System.out.println(a[i] + "---" + q1 + " " + q2 + " " + r1); } //System.out.println(sum + ""); if(sum < sum1) sum1 = sum; } System.out.println(sum1); } } }

Abhinav_Dhanak02 + 0 comments Thanks for the code and explaination.

liam_meck + 4 comments SPOILER! Hint if you're stuck:

Giving chocolate to everyone except the chosen person is the same as taking chocolate away from the chosen person. We don't care about how much chocolate they end up with, only that each person's amount is equal.

For example:

`Give 5: 1 3 5 6 8 5 <- Take 5: 1 3 5 1 3 0 <- The two results are the same relative to themselves, just shifted: 1 3 0 + 5 5 5 --------- 6 8 5`

The problem becomes much simpler now.

Also remember to look for caching opportunities.

magda_sadlo + 0 comments Great remark, when you re-state the problem like this, it becomes easy. Thanks!

harryapotter + 0 comments Thank you very much. When explain like that, the problems seem easier than

de_vika + 0 comments I did the same thing but my last testcase is going wrong :/

jubin_kuriakose + 1 comment How does it make this easier?

de_vika + 0 comments Yes this helps us to change our range update to a single element update !

todd24 + 2 comments Why does the problem say 3 chocolates when all of the discussions and editorial use 2?

davidbrucecohen + 1 comment The frustrating thing is that if you do the problem with 1,3,5 (as it is currently written) rather than 1,2,5 (which it should be), then your answers will end up being quite close to correct.

kevinwang + 0 comments yeah, really weird. Don't know why they changed both the problem statement and the examples in the problem statement to use {1,3,5}, but all the testcases are still {1,2,5}.

littlepirate + 1 comment @amititkgp @hackerrank, any ideas on why this is done?

agarus + 0 comments To "try" to knock out gready approach.

askkamalnayan + 0 comments The question statement is wrong. Actually the coins have values {1,2,5} and not {1,3,5}.

Sort 333 Discussions, By:

Please Login in order to post a comment