Visual Solutions to Algorithms: The Staircase
If you've ever visited Hackerrank, you are probably familiar with the classic warm-up problem known as The Staircase. But did you know you can solve for it without needing any code at all?
Well, by solve, I mean "arrive at the correct algorithm"...you still need to type it out and have it run! So, first, let's go over what the problem wants:
Consider a staircase of size n = 4:
#
##
###
####
Observe that its base and height are both equal to n, and the image is drawn using # symbols and spaces. The last line is not preceded by any spaces.
Write a program that prints a staircase of size n.
Input Format
A single integer, n, denoting the size of the staircase.
Output Format
Print a staircase of size n using # symbols and spaces.
Note: The last line must have 0 spaces in it.
Sample Input
6
Sample Output
#
##
###
####
#####
######
Explanation
The staircase is right-aligned, composed of # symbols and spaces, and has a height and width of n=6.
So, we already know what we need for input, but what else can we get from this? We need to account for spaces. So, we take input n, and based on that, we must print n lines, but only the nth line should have n amount of symbols. Some recursion will be involved, but what's the most efficient instruction we can give it? Remember, this is supposed to be an easy problem.
It's easier if we think of this in terms of individual spaces, rather than individual lines. My approach was to draw a staircase, and my mind put a grid around it. Then, I drew an actual grid around it. Here is an MS Paint rendition of what I mean:
Now that we see this as a grid, we can understand this in terms of rows and columns. So, we have rows "i" and columns "j". It's also important to note that these are 0-indexed in code, so the grid must be seen as:
0 1 2
0
1
2
So, now it's time to start looping:
for (i = 0; i <n; i++)
{
for(j = 0; j <n; j++)
{
//Now what?
}
}
All that's left is the algorithm. Since we have a grid, adjusted to the size specified by n, how does it know which spaces to print the #? In the drawing, we have the following spaces filled up: (i=0,j=2), (i=1,j=1), (1,2), (2,0), (2,1), (2,2).
We can see that these spaces where the symbol is drawn are all where j >= i - n - 1. Even if you have a staircase made with an input of 6, this still holds true. In the spaces where it doesn't, we just print a space. So the final answer, in C++, looks like:
for (i = 0; i <n; i++)
{
for(j = 0; j <n; j++)
{
if(j >= i - n - 1)
cout << "#";
else
cout << " ";
}
}
See? Actually very simple and easy! Sometimes it helps to draw out the problem before jumping into the code right away =).
