Down to Zero II

This post is related to HackerRank challenge “Down to Zero II” which seems to require dynamic programming to get it solved. I tried a top down (which I modified into a bottom up) approach. Sorry but I overwrote the code for my first approach. Should have started a new method or saved it in Git.

Please take a look at the challenge at:  https://www.hackerrank.com/challenges/down-to-zero-ii

The idea of Dynamic Programming is to attempt to use existing solutions instead of computing them again each time a similar problem needs to be solved. For example, if you have computer a factor for 32 = 2 * 2 * 2 * 2 * 2 (or 2^5), then when you are computing 64 = 32 * 2 (or 2^6) you could just look up the result associated with 32 and incorporate it into the solution of 64. Continue reading “Down to Zero II”

Dynamic Programming

down_to_zeroIn the process of practicing and refreshing algorithms, I am looking at the Down to Zero II challenge (https://www.hackerrank.com/challenges/down-to-zero-ii) from HackerRank.

After reading the challenge a few times and taking a look at some of the discussions I decided to do it in two steps. My first approach is what I would call brute force. It seems to work in some cases but as expected it does not provide an optimal solution in others. The second approach and what seems to be the right one will be discussed in the next post. That approach uses dynamic programming. Continue reading “Dynamic Programming”