Today is January 21, 2021. Yesterday was the United States presidential inauguration. As you know I do not like politics. That said; I like facts so later when something does not seem right I will be able to make my own educated decision as to what the real reasons were for the results we are observing. That said; I would invite you to find out about the executive orders signed yesterday by Joe Biden. Then put aside your political associations, and think what would the effects of the executive orders be for the future of the USA and for the citizens of the USA and the free and democratic world?
As I was generating this post I checked and the blog has exceeded the 6,000 followers mark!!! Thank you all for making this happen. Hopefully it is having some type of positive impact on your learning journey.
Yesterday or early today I received a message from HackerRank suggesting a problem. Since I had some time between a completed task for work and lunch, I decided to give it a try. The problem is ranked EASY so it should not take too much time so solve. The problem is named Halloween Party. It will seem quite appropriate after we read the description.
Alex is attending a Halloween party with his girlfriend, Silvia. At the party, Silvia spots the corner of an infinite chocolate bar (two dimensional, infinitely long in width and length). If the chocolate can be served only as 1 x 1 sized pieces and Alex can cut the chocolate bar exactly K times, what is the maximum number of chocolate pieces Alex can cut and give Silvia? Input Format: The first line contains an integer T, the number of test cases. T lines follow. Each line contains an integer K. Output Format: T lines; each line should contain an integer that denotes the maximum number of pieces that can be obtained for each test case. Constraints: o 1 <= T <= 10 o 2 <= K <= 10^7 Note: Chocolate must be served in 1 x 1 sized pieces. Alex can't relocate any of the pieces, nor can he place any piece on top of another.
The problem is very well defined. Take a look at the diagram included in the HackerRank site. We have an infinitely large chocolate bar (who does not like chocolate?). The idea is that we are given the number of cuts that we can make. Each piece of chocolate must be 1 x 1 units. We need to cut as many pieces as possible given the number of cuts we can make.
If you make no cuts you do not end up with any 1 x 1 pieces. If you make a single cut on the vertical or horizontal direction, you end with an infinitely long 1 x infinity piece. If you make a second cut on the 1 x infinity piece in order to get a 1 x 1 piece you end up with a single piece.
At this time please take a few minutes figuring out on a piece of paper how we can get the maximum number of 1 x 1 pieces to make some points with Silvia. Go ahead; I will wait for you …
… You are back!
The math is not too complicated. Just experiment with 2, 3, … number of cuts so you can determine mathematically what you are looking for.
If you are not new to my blog, you know that I like to solve the problems on my computers at home. HackerRank provides a test scaffolding which will be used to test our code. I will develop the solution on a Windows 10 computer using the Java programming language and the VSCode IDE.
/*
* Complete the halloweenParty function below.
*/
static long halloweenParty(int k) {
/*
* Write your code here.
*/
}
The signature for the solution indicates that we are to write code inside the halloweenParty() function / method with has as an argument the total number of cuts we can perform.
9 0 1 2 3 4 5 6 7 8 main <<< T: 9 main <<< k: 0 main <<< pieces: 0 main <<< k: 1 main <<< pieces: 0 main <<< k: 2 main <<< pieces: 1 main <<< k: 3 main <<< pieces: 2 main <<< k: 4 main <<< pieces: 4 main <<< k: 5 main <<< pieces: 6 main <<< k: 6 main <<< pieces: 9 main <<< k: 7 main <<< pieces: 12 main <<< k: 8 main <<< pieces: 16
Let’s see if we can follow the screen capture for the test scaffolding we wrote. To be honest I did not take time to look at the code provided by HackerRank. It might be simpler and nicer than what I have. What can I say.
The first input number indicates the number of test cases we will process in this batch. The following numbers are processed one by one. Each line is a test case. The number indicates the total number of cuts we can perform on our magical chocolate bar.
Note that all the values provided by HackerRank are included in my list. I added some end cases to make sure we do not have issues with them.
Our test code seems to read and display each argument followed by the associated response which is labeled as the number of pieces we cut. The results for the provided test cases by HackerRank seem to match. Perhaps we got it right. Will find out when the code is submitted.
/**
* Test scaffolding.
*
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** open buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** read number of test cases ****
int T = Integer.parseInt(br.readLine().trim());
// ???? ????
System.out.println("main <<< T: " + T);
// **** loop once per test case ****
for (int t = 0; t < T; t++) {
// **** read the number of cuts ****
int k = Integer.parseInt(br.readLine().trim());
// ???? ????
System.out.println("main <<< k: " + k);
// **** compute and display result ****
System.out.println("main <<< pieces: " + halloweenParty(k));
}
// **** close buffered reader ****
br.close();
}
Our test scaffolding is simple. We use a buffered reader to read each value at a time. When we enter the loop we have the total number of test cases so we only need to read the number of cuts. Once we have read and displayed the value we call the function in question and display the returned value (as pieces).
/*
* Complete the halloweenParty function below.
* v == vertical cuts
* h == horizontal cuts
*/
static long halloweenParty(int k) {
// **** sanity check(s) ****
if (k < 2)
return 0;
// **** distribute the cuts (k = v + h) ****
long v = k / 2;
long h = k - v;
// **** compute and return the number of pieces ****
return v * h;
}
We start by performing some sanity checks. Let’s think how many 1 x 1 pieces can we get with no cuts? The answer is 0. The same holds true if we have a single cut. When we get to 2 cuts, if we made them 1 unit from the horizontal edge and 1 unit from the vertical edge, then we have 1 piece.
We need to figure the maximum number of pieces to get with the number of cuts we have. If the number is divisible by two (i.e., 4) we could make 2 cuts in each direction for a total of 4 1 x 1 pieces. If the number is not even (i.e., 5) then we could get 2 on one direction and 3 in the other for a total of 6 pieces. With this in mind we can come up with the next two statements.
The only thing missing is to generate the number of pieces. That is computed by multiplying the number of cuts.
The code was accepted by HackerRank.
Hope you enjoyed solving this problem as much as I did. 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 help out 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 e-mail message. I will reply as soon as possible.
Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge and enhance your developer toolset.
One last thing, many thanks to all 6,008 subscribers to this blog!!!
Keep safe during the COVID-19 pandemic and help restart the world economy. I believe we can all see the light at the end of the tunnel.
Regards;
John
john.canessa@gmail.com