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.
Following is the output of a modified solution for the sample input for this challenge:
1 3 main <<< duration: 4 ms 3->2->1->0 : 3 main <<< totalDuration: 4 ms
The solution just calls to display the number of steps needed to go from 3 to 0.
The above screen capture illustrates the actual steps. Number 3 needs to be converted to 2 (3 – 1 ==1) to proceed. Number 2 needs to be converted to 1 (2 – 1 = 1) to proceed. Finally number 1 needs to be converted to 0 (1 – 1 = 0) which ends the process. The example just illustrates the second operation that may be taken at each step (decrease the value of N by 1). It does not illustrate the operation if N = a * b (a != 1, b != 1), we change N = max(a, b). If you read all the entries in the discussion section, that created confusion. It is important to properly state requirements before developing any piece of software.
Earlier this week I was talking with a couple colleagues and the questions of what would you do when starting an Agile project and all requirements are not specified?
The software engineering answer is not to write software without requirements. It is instead to elicit requirements from the project owner regardless of whether there is formal requirements documentation or not.
In Agile gathering requirements is definitely the first priority, but you don’t necessarily need to get all of the customer’s needs noted up front. The risk is of course is that you might miss some vital piece of information and render the system architecture useless if you have not managed to have the right sort of conversations with the customer, however it is not unusual to define a product and even get much of the development out of the way, while deferring the major system architecture decisions until the last possible moment. This is a lean development approach which is meant to ensure that you do not commit to a potentially incompatible architecture too early in the product development until one has completed the requirements process.
Most times architects and analysts need to spend additional time during the development process with the customer to help the customer clarify their needs. Most often, the customer calls you in early to depend on your expertise to define their requirements as the customer doesn’t always have the necessary expertise or knowledge of the software development process.
All these said; it is possible to start a software development process without a full understanding of the requirements. Requirements may be clarified during the process. This type of situation calls for analysts, architects and senior developers to have experience managing the project with incomplete requirements. Failure to do so tends to produce incomplete and unreliable products.
In my professional life I have worked on several projects were few requirements were understood and documented. The key is to run the project in a fixed number of cycles (typically 3) and complete the first production version in 9 to 12 months.
Getting to the topic of this blog, the description of the challenge leaves a lot to be desired. I did implement the software twice using the top-down and bottom-up approaches. Because of that I spent more time than was required to solve it. As a reference I suggest to read chapter 15 Dynamic Programming in the book Introduction to ALGORITHMS third edition by Thomas Cormen et al.
Following is a screen capture of the console from the Eclipse IDE:
26 1 2 3 4 7 12 16 34 86 125 168 256 257 1000 2436 11565 11566 46264 214567 225604 603900 808707 812849 833352 999999 1000000 main <<< duration: 6 ms 1->0 : 1 main <<< duration: 0 ms 2->1->0 : 2 main <<< duration: 0 ms 3->2->1->0 : 3 main <<< duration: 0 ms 4->2->1->0 : 3 main <<< duration: 0 ms 7->6->3->2->1->0 : 5 main <<< duration: 0 ms 12->4->2->1->0 : 4 main <<< duration: 0 ms 16->4->2->1->0 : 4 main <<< duration: 0 ms 34->17->16->4->2->1->0 : 6 main <<< duration: 0 ms 86->85->84->12->4->2->1->0 : 7 main <<< duration: 1 ms 125->25->5->4->2->1->0 : 6 main <<< duration: 1 ms 168->84->12->4->2->1->0 : 6 main <<< duration: 0 ms 256->16->4->2->1->0 : 5 main <<< duration: 0 ms 257->256->16->4->2->1->0 : 6 main <<< duration: 1 ms 1000->40->8->4->2->1->0 : 6 main <<< duration: 3 ms 2436->84->12->4->2->1->0 : 6 main <<< duration: 11 ms 11565->257->256->16->4->2->1->0 : 7 main <<< duration: 0 ms 11566->11565->257->256->16->4->2->1->0 : 8 main <<< duration: 39 ms 46264->46263->6609->6608->112->16->4->2->1->0 : 9 main <<< duration: 393 ms 214567->9329->9328->176->16->4->2->1->0 : 8 main <<< duration: 30 ms 225604->56401->56400->240->16->4->2->1->0 : 8 main <<< duration: 1429 ms 603900->9900->132->12->4->2->1->0 : 7 main <<< duration: 1015 ms 808707->1717->1716->132->12->4->2->1->0 : 8 main <<< duration: 22 ms 812849->812848->1616->1615->85->84->12->4->2->1->0 : 10 main <<< duration: 120 ms 833352->5342->5341->109->108->12->4->2->1->0 : 9 main <<< duration: 988 ms 999999->2457->63->9->3->2->1->0 : 7 main <<< duration: 1 ms 1000000->20000->160->16->4->2->1->0 : 7 main <<< totalDuration: 4060 ms
The input numbers (26) are mostly based on numbers that were collected from the discussions of this challenge. I added the time it took to process an entry and the total time it took to process the first to the last entry (4.02 seconds). In addition, for each number there is a sequence of the steps taken by the program to reduce the number to 0.
Using the bottom up approach meant to generate in an array (I named it cache[]) the solutions for each number between [0 – 1000000]. A second array (I named it next[]) is used to keep track of the numbers being reduced in order for a method (showPath()) to be able to display the sequence. This was done to allow me to understand the issues other developers encountered and be able to verify and post suggestions.
Following is the Java code for my solution which was accepted by HackerRank:
package john.canessa.down.to.zero;
import java.util.Scanner;
public class Solution {
final static int MAX_N = 1000001;
// **** ****
static int[] cache = null;
static int[] next = null;
static int minFactor = 3;
/**
* initialize the cache for bottom up approach
*/
static void cacheInitBottomUp(int n) {
// **** ****
if ((n < 0) || (n >= MAX_N)) {
System.err.println("cacheInitBottomUp <<< unexpected n: " + n);
return;
}
// **** allocate arrays (if needed) ****
if (cache == null) {
// **** allocate arrays ****
cache = new int[MAX_N];
next = new int[MAX_N];
// **** fill cache [0 : 2] ****
cache[2] = 2;
cache[1] = 1;
cache[0] = 0;
// **** fill next [0 : 2] ****
next[2] = 1;
next[1] = 0;
next[0] = -1;
}
// **** ****
int a = 0;
int b = 0;
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
int minVal = Integer.MAX_VALUE;
// **** fill cache and next arrays ****
for (int i = minFactor; i <= n; i++) {
// **** process each factor [3 : i] ****
minVal = Integer.MAX_VALUE;
for (int factor = 1; (factor * factor) <= i; factor++) {
// **** if not a factor then skip ****
if ((i % factor) != 0) {
continue;
}
// **** ****
a = i / factor;
b = i / a;
// **** ****
if ((a != 1) && (b != 1)) {
max = Math.max(a, b);
min = 1 + cache[max];
} else {
min = 1 + cache[i - 1];
}
// **** update the minimum value (if needed) ****
if (min < minVal) { minVal = min; if ((a != 1) && (b != 1)) { next[i] = max; } else { next[i] = i - 1; } } } // **** update the cache entry **** cache[i] = minVal; } // **** update minFactor (if needed) **** if (n > minFactor) {
minFactor = n;
}
}
/**
* look up n in the cache (if in range)
*/
static int bottomUp(int n) {
if ((n >= 0) && (n < MAX_N)) { return cache[n]; } else { return -1; } } /** * show the path from n to 0 */ static void showPath(int n) { // **** **** if (n == 0) { System.out.print(n); } else { System.out.print(n + "->");
}
// **** ****
while (n > 0) {
System.out.print(next[n]);
n = next[n];
if (n > 0) {
System.out.print("->");
}
}
// **** ****
System.out.print(" : ");
}
/**
* solution
*/
public static void main(String[] args) {
long totalDuration = 0;
Scanner sc = new Scanner(System.in);
int Q = sc.nextInt();
for (int q = 0; q < Q; q++) {
int n = sc.nextInt();
long start = System.currentTimeMillis();
cacheInitBottomUp(n);
int answer = bottomUp(n);
long end = System.currentTimeMillis();
long duration = end - start;
System.out.println("main <<< duration: " + duration + " ms");
totalDuration += duration;
// **** display selected path ****
showPath(n);
// **** display answer ****
System.out.println(answer);
}
System.out.println("main <<< totalDuration: " + totalDuration + " ms");
sc.close();
}
}
Note the use of the minFactor variable which is used to optimize the complete run. The program initializes in steps (bottom – up) the range that is needed to solve the maximum number entered in the list so far. The range in the challenge is defined a 0 <= N <= 10^6. The entries in the cache[] and next[] arrays are filled from 0 to the current maximum number. Please note that for simplicity the numbers in my test are in ascending order. That allows a faster response when processing smaller numbers.
With the cache[] array complete, further calls on additional numbers is a straight look-up in an array. That operation takes less than a millisecond.
If you have comments or questions regarding this entry or any other post in this blog, please do not hesitate and send me a message via email. Will keep you name in confidence unless you explicitly tell me the contrary.
John
John.canessa@gmail.com
Follow me on Twitter: @john_canessa