Down to Zero – Revisited

!!! NOTE !!!

Not sure what happens with the formatted code which seems to display well and sometimes it does not. The good thing is that the entire code is in my GitHub repository. Sorry about the inconvenience. If you have a formatter for Word Press that you like and is reliable, please let me know.

I received a message from a reader of my blog requesting some clarification on my original solution and associated post Down to Zero II. The associated post was from 2016. The initial code was not in my GitHub repository. Sorry about that.

After reading the message (which I keep private unless told otherwise) I went to GitHub and created a new repository. I added a short and simple README.md file and cloned the repo to one of my Windows 10 computers.

I then copied the original solution.java file and opened it using VSCode. The original code was developed using the Eclipse IDE. In the past year or so I have switched to VSCode for C++, Java, and Python.

If interested in the description of the problem please take a look at Down to Zero II.

2
3
4

main <<< duration: 3 ms 3->2->1->0 : 3
main <<< duration: 0 ms 4->2->1->0 : 3
main <<< totalDuration: 3 ms


1
500

main <<< duration: 6 ms 500->25->5->4->2->1->0 : 6
main <<< totalDuration: 6 ms


1
1000

main <<< duration: 7 ms 1000->40->8->4->2->1->0 : 6
main <<< totalDuration: 7 ms


1
100000

main <<< duration: 74 ms 100000->20000->160->16->4->2->1->0 : 7
main <<< totalDuration: 74 ms

The first number indicates the number of test cases. Each test case contains a single number which is contained in separate lines.

I have added a mechanism to compute and display the time that the code takes to execute. That code is not part of the solution and as we will see shortly, is part of the test scaffolding.

The following line displays the path from the specified number down to 1. Displaying the path is not part of the solution as specified by HackerRank. The solution requires the number of steps which in both examples is 3.

The other three test cases are to check the time the code takes to execute for larger numbers.

	/**
	 * Test scaffolding.
	 */
	public static void main(String[] args) {

		// ????? ????
		long totalDuration	= 0;

		// **** open scanner ****
		Scanner sc			= new Scanner(System.in);

		// **** read number of queries ****
		int	Q 				= sc.nextInt();
		
		// **** loop once per query ****
		for (int q = 0; q < Q; q++) {

			// **** read the value ****
			int n			= sc.nextInt();
					
			// ???? start time????
			long start 		= System.currentTimeMillis();

			// **** function to complete ****
			int answer = downToZero(n);

			// ???? end time ????
			long end 		= System.currentTimeMillis();

			// ???? compute duration ????
			long duration	= end - start;
			System.out.println("main <<< duration: " + duration + " ms");
			totalDuration 	+= duration;
			
			// ???? display selected path ????
			showPath(n);
			
			// **** display answer ****
			System.out.println(answer);
		}
		
		// ???? display duration ????
		System.out.println("main <<< totalDuration: " + totalDuration + " ms");

		// **** close scanner ****
		sc.close();
	}

The main method implements the test scaffolding. It is an edited version of the original method edited to implement timing and adhere to have the implementation of the actual solution in the downToZero method.

	/**
	 * Function to complete.
	 */
	static int downToZero(int n) {
		cacheInitBottomUp(n);
		return bottomUp(n);
	}

The method performs two tasks. The first line initializes some variables and the second implements a bottom up approach to compute the result.

	/**
	 * Show the path from n to 0
	 * This method is not part of the solution.
	 * It is an enhancement.
	 */
	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(" : ");
	}

This method is not part of the solution. It is used to display the actual path from the specified n down to 1.

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

This method returns the number of steps generated to get from n to 1. If not possible, the method returns -1.

	/**
	 * initialize the cache for bottom up approach
	 */
	static void cacheInitBottomUp(int n) {
		
		// **** perform sanity check(s) ****
		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;
		}
	}

This method initializes the variables and loops filling in the cache which will be used to compute the result. Note that the code was described in my original post for which I have provided a link at the start of this post.

	// **** ****
	final static int MAX_N		= 1000001;

	// **** ****
	static int[] cache 			= null;
	static int[] next			= null;
	
	static	int minFactor		= 3;

This last code snippet declares the variables that are used to solve the problem.

# **** ****
C:\Users\johnc\workspace0\DownToZeroII>git status
On branch master
Your branch is up to date with 'origin/master'.

Untracked files:
  (use "git add <file>..." to include in what will be committed)
        Solution.java

nothing added to commit but untracked files present (use "git add" to track)

# **** ****
C:\Users\johnc\workspace0\DownToZeroII>git add Solution.java

# **** ****
C:\Users\johnc\workspace0\DownToZeroII>git status
On branch master
Your branch is up to date with 'origin/master'.

Changes to be committed:
  (use "git restore --staged <file>..." to unstage)
        new file:   Solution.java

# **** ****
C:\Users\johnc\workspace0\DownToZeroII>git commit -m "complete solution"
[master e9957f4] complete solution
 1 file changed, 195 insertions(+)
 create mode 100644 Solution.java

# **** ****
C:\Users\johnc\workspace0\DownToZeroII>git status
On branch master
Your branch is ahead of 'origin/master' by 1 commit.
  (use "git push" to publish your local commits)

nothing to commit, working tree clean

# **** ****
C:\Users\johnc\workspace0\DownToZeroII>git push origin master
Enumerating objects: 4, done.
Counting objects: 100% (4/4), done.
Delta compression using up to 12 threads
Compressing objects: 100% (3/3), done.
Writing objects: 100% (3/3), 1.52 KiB | 1.52 MiB/s, done.
Total 3 (delta 0), reused 0 (delta 0)
To https://github.com/JohnCanessa/DownToZeroII.git
   48a55ae..e9957f4  master -> master

# **** ****
C:\Users\johnc\workspace0\DownToZeroII>git status
On branch master
Your branch is up to date with 'origin/master'.

nothing to commit, working tree clean

# **** ****
C:\Users\johnc\workspace0\DownToZeroII>git log
commit e9957f457eea194091ec2182fe71e6d935346967 (HEAD -> master, origin/master, origin/HEAD)
Author: JohnCanessa <john.canessa@gmail.com>
Date:   Thu May 7 15:18:15 2020 -0500

    complete solution

commit 48a55aeef86acdd244eb1bac52ddf1e83055dd52
Author: John Canessa <8019504+JohnCanessa@users.noreply.github.com>
Date:   Thu May 7 14:39:41 2020 -0500

    Create README.md

After checking this version of the code in HackerRank, passing the 14 test cases and sending out a Tweet from HackerRank, I pushed the updated solution to my repository in GitHub.

The entire code for this project can be found in my GitHub repository.

If you have comments or questions regarding this, or any other post in this blog, or if you would like for me to serve of assistance with any phase in the SDLC (Software Development Life Cycle) of a project associated with a product or service, please do not hesitate and leave me a note below. If you prefer, send me a private message using the following address:  john.canessa@gmail.com. I will reply as soon as possible.

Keep on reading and experimenting. It is the best way to learn, refresh your knowledge and enhance your developer toolset!

One last thing, many thanks to all 861 subscribers to my blog!!!

John

Twitter:  @john_canessa

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.