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.

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.

Cookie support is required to access HackerRank

Seems like cookies are disabled on this browser, please enable them to open this website

## Equal

You are viewing a single comment's thread. Return to all comments →

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.