[Solution]Problem 29: Arranging Coins in Staircase[Netflix]
Lists, Math, Dynamic Programming, Recursion
How’s it grooving my favorite coders,
Time to go over the solution to the problem discussed yesterday. Hope you’re excited. This post/email will be very interesting because along with the answer, we will actually be discussing some pretty interesting things related to time complexity.
Problem
This problem was asked by Netflix.
You have n
coins and you want to build a staircase with these coins. The staircase consists of k
rows where the ith
row has exactly i
coins. The last row of the staircase may be incomplete.
Given the integer n
, return the number of complete rows of the staircase you will build.
For example, given n=5 you will return 2.
[FREE SUBS]To buy the solution for this problem, use any of the following links. The price is 3 USD. Once you send the payment, message me on IG, LinkedIn, Twitter, or Email:
Venmo: https://account.venmo.com/u/FNU-Devansh
Paypal: paypal.me/ISeeThings
Step 1: Input and Outputs
A staple approach of this newsletter, the first thing we will cover is the analysis of what exactly this question is asking. It will help us find hints about the solution, spot nuances, and allow us to analyze our performance at the end. Let’s begin our analysis.
Input—> We get an integer n. Since n is supposed to be the number of coins, we know it is non-negative (unless we want to allow debt!!!). Can it be 0? Ask the interviewer these questions. Such clarifying questions are low-hanging fruit. Always pluck the low-hanging fruit.
Output—> We want to return the maximum number of complete rows we can create. This means two things. We can’t always return 0 (we can always create 0 rows) and call it a day (this might seem silly, but paying attention to wording is very important). More importantly, we want to truncate whatever calculation we do at the end. This will make sure we always get the correct number.
This process is very simple for this problem. So it won’t take more than 2 minutes (at most). However, it is important to do as a way to drill the habit in. Now let’s work out the solution
Step 2: Looking at the staircases
We are given a pretty interesting condition. We know that the ith row will contain i coins. This tells us two things. Firstly, to complete the ith row we need to have atleast n coins left. Secondly, once let’s say we have completed i rows. This means that up to this point, we have used (1+2+3…+i) coins. Simple math tells us that we will therefore have n-(1+2+3…+i) coins left.
The simple approach would be something like this:
row,i=0,0
while n>=i{
n-=i
i+=1
}
return i
Obviously if n==0 then we want to return 0.
This approach is going to be close to square root(n). Why not linear? Because, as i grows, the value of n will reduce even faster. We will cover the rationale for this on a Math Monday, so make sure you check in for them. How can we improve this? By doing some simple simplifications
Keep reading with a 7-day free trial
Subscribe to Technology Made Simple to keep reading this post and get 7 days of free access to the full post archives.