We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.

- Prepare
- Algorithms
- Dynamic Programming
- Equal
- Discussions

# Equal

# Equal

#### Sort by

recency

#### |

#### 451 Discussions

#### |

Please Login in order to post a comment

For those generating solution values < than the test cases provided. This is because you are evaluting a convergence towards MAX and not MIN (or some other convergence value in the array). This isn't allowed because the problem states she has to ADD chocolates on each move -> she is not allowed to TAKE away chocolates from all but one in order to equalise.

This question is misleading! When I test my code below to equate all numbers in the list and count number of operations, I get the minimum number of operations compared to the ones gotten on their test cases, so my code does not pass their test cases!

O(n) no dynamic programming, no induction. this question is stupid because it makes u think about it with dynamic programming/induction, pointing u in the wrong direction, wasted so much of my time. but the answer has nothing to do with either

https://rohangupta-3817.medium.com/hackerrank-dp-equal-5adc78771571Great explanation here:My solution:

For all the Java/C++/C users - this is a fantastic problem which enforces a good amount of time worth investing, to solve this simple yet "deep under surface" dynamic programming problem.

Two concepts which probably everyone understood now - * Adding 1, 2 or 5 to all but one element in an array, is same as "subtracting" the same from that "excluded" element only, while sparing others. This ensures that the "net" difference between the elements remain the same. * The problem would have been much simpler if we knew the target element where the array ultimately would converge (i.e., comprise of all same elements), which would serve as the base case (if recursive approach is employed). But what is that value ...?

Turns out, if we rely only on recursive-with-memo approach, (especially with Python) chances are there for either exhaustion of stack calls or a Time limit issue (TLE). So can we formulate a tabulation based solution ? If so what can be the deterministic values we can utilize as the bounding limits for our solution ?

It turns out, we can utilize tabulation, with proper limits, that too with a complexity of O(n), where n is the size of the array.

The upper limit can be utilized as 1000, which is the initial max capacity as mentioned. The lower limit, to which every element must converge - is the question. It turns out - the worst case scenario can be -5 (if 5 is deducted from 0 elemental value). We can then use a 1006x1006 lookup matrix (with decimal values -5 to 1000, 0 indexing) with every diagonal element value 0, and INF for all j < i. Every element lookup(i,j) denotes the min operations required for the jth value to converge to i. The objective is to find the converging value 'i' for which the sum of all the operations required to converge every element is minimized.