In the process of practicing and refreshing algorithms, I am looking at the Down to Zero II challenge 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