# Dynamic Programming

In 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.

The output from the console from my Eclipse IDE follows:

1

3

show <<< n: 3 stack: 3

show <<< n: 2 stack: 2

The answer is correct and the explanation for it follows:

3->2->1->0

The show method displays the stack of factors for each step. We start with N = 3 and given that N = a * b where a != 1 and b != 1 is not possible we decrement by one and set N to two. This is the first operation. We then repeat with N = 2 and decrement N = 1 while incrementing the count to two. Finally we test N = 1 and decrement N = 0 reaching the goal. The count is now set to three.

Take a look at the following sequence which seems to work but then …

1

4

1

16

1

256

1

257

1

11565

The sequence is correct as illustrated by the following:

11565 ->257 ->256 ->16 ->4->2->1->0

The world changes when we try the following:

1

11566

11566->11565->257->256->16->4->2->1->0

A better answer is eight (not 10). The reason is quite obvious when you ran the code displaying the stack. I am including such runs because they contain too many lines.

The code for my first attempt which I have not submitted to the challenge follows:

package john.canessa.down.to.zero;

import java.util.Scanner;

import java.util.Stack;

public class Solution {

// **** ****

static Node   root   = null;

/**

* reduce n down to zero

* @throws Exception

*/

static int reduce (Node node) throws Exception {

int    minLevel = Integer.MAX_VALUE;

// **** get n from the node ****

int    n = node.n;

// **** ****

if (n <= 1) {

return node.level;

}

// **** get the level from the node ****

int level = node.level;

level++;

// **** populate stack with all factors of n ****

Factors factors = new Factors();

Stack<Integer> factorStack = factors.factors(n);

factors.show(factorStack);

// **** ****

for (int i = 0; !factorStack.isEmpty(); i++) {

int f = factorStack.pop();

int a = f;

int b = n / f;

// **** reduce ****

if ((a != 1) && (b != 1)) {

} else {

}

// **** reduce new node ****

minLevel = Math.min(reduce(node.nodes.get(i)), minLevel);

}

// **** ****

return minLevel;

}

/**

* build tree with nodes reducing value to zero

* @throws Exception

*/

static void treeToZero(int n) throws Exception {

// **** root for the tree ****

root = new Node(n);

// **** build the tree ****

System.out.println(“treeToZero <<< answer: ” + reduce(root));

}

/**

* solution which not uses the proper approach which is dynamic programming

* @throws Exception

*/

public static void main(String[] args) throws Exception {

Scanner sc = new Scanner(System.in);

int    Q = sc.nextInt();

for (int q = 0; q < Q; q++) {

int N  = sc.nextInt();

treeToZero(N);

}

sc.close();

}

}

My purpose for solving challenges is to refresh and on some cases learn something new. To refresh the approach that seems to be the one that will provide optimal solutions I referred to chapter 15 Dynamic Programming in Introduction to ALGORITHMS third edition by Thomas H. Cormen et al. As usual I would recommend to any individual involved in the SDLC to purchase the book, periodically read and experiment with some of the exercises. Remember the saying: We are what we repeatedly do. Excellence, then, is not an act, but a habit (Aristotle).

The definition in the book makes a good point that “Programming” in Dynamic Programming refers to a tabular method, not writing computer code. Dynamic programming should be used when the subproblems share subsubproblems.

Take a look at the following output from the current code:

1

16

show <<< n: 16 stack: 2 4 8 16

show <<< n: 15 stack: 3 5

show <<< n: 5 stack: 5

show <<< n: 4 stack: 2 4

show <<< n: 3 stack: 3

show <<< n: 2 stack: 2

show <<< n: 2 stack: 2

show <<< n: 5 stack: 5

show <<< n: 4 stack: 2 4

show <<< n: 3 stack: 3

show <<< n: 2 stack: 2

show <<< n: 2 stack: 2

show <<< n: 8 stack: 2 4 8

show <<< n: 7 stack: 7

show <<< n: 6 stack: 2 3

show <<< n: 3 stack: 3

show <<< n: 2 stack: 2

show <<< n: 3 stack: 3

show <<< n: 2 stack: 2

show <<< n: 4 stack: 2 4

show <<< n: 3 stack: 3

show <<< n: 2 stack: 2

show <<< n: 2 stack: 2

show <<< n: 4 stack: 2 4

show <<< n: 3 stack: 3

show <<< n: 2 stack: 2

show <<< n: 2 stack: 2

show <<< n: 4 stack: 2 4

show <<< n: 3 stack: 3

show <<< n: 2 stack: 2

show <<< n: 2 stack: 2

show <<< n: 8 stack: 2 4 8

show <<< n: 7 stack: 7

show <<< n: 6 stack: 2 3

show <<< n: 3 stack: 3

show <<< n: 2 stack: 2

show <<< n: 3 stack: 3

show <<< n: 2 stack: 2

show <<< n: 4 stack: 2 4

show <<< n: 3 stack: 3

show <<< n: 2 stack: 2

show <<< n: 2 stack: 2

show <<< n: 4 stack: 2 4

show <<< n: 3 stack: 3

show <<< n: 2 stack: 2

show <<< n: 2 stack: 2