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

treeToZero <<< **answer: 3**

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

treeToZero <<< **answer: 3**

1

16

treeToZero <<< **answer: 4**

1

256

treeToZero <<< **answer: 5**

1

257

treeToZero <<< **answer: 6**

1

11565

treeToZero <<< **answer: 7**

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

treeToZero <<< **answer: 10**

A possible correct solution (not found by the current code) follows:

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)) {

node.nodes.add(**new** Node((**int**)Math.*max*(a, b), level));

} **else** {

node.nodes.add(**new** Node(n – 1, level));

}

// **** 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

treeToZero <<< answer: 4

The **reduce()** method is called multiple times with **repeated** values for 2, 3, 4, 5, … What a waste of resources. In this case the software produced an optimal solution, but as one can check, the algorithm does not always produce an optimal solution.

If you have comments or questions regarding this or any other blog post, please send me an email message. I will keep your name in confidence unless you explicitly allow me to disclose it.

John

**john.canessa@gmail.com**

Follow me on Twitter: **@john_canessa**