Last Updated: 26 Feb, 2021
Hurdle Game
Easy
Asked in companies
Once Kevin is playing a hurdle game in which he has to jump some hurdles to clear a particular level. Each level ‘i’ has ‘i’ hurdles (for example, level 6 has 6 hurdles).
You are provided with the total number of hurdles that Kevin has jumped, you have to tell how many levels he has cleared.
Note :
Kevin has played this game once. He can only reach the level ‘i’ if and only if he has already cleared the level (‘i’ - 1).
Input Format :
The first line contains a single integer ‘T’ representing the number of test cases.
The first line of each test case will contain a single integer ‘N’ which represents the total number of hurdles that Kevin has jumped.
Output Format :
For each test case, print an integer denoting the number of levels that Kevin has cleared.
Output for every test case will be printed in a separate line.
Note :
You don’t need to print anything; It has already been taken care of. Just implement the given function.
Constraints :
1 <= T <= 50
0 <= N <= 10 ^ 8
Time limit: 1 sec
Approaches
The basic idea is to iterate through all the levels and keep subtracting the hurdles that Kevin has jumped. The steps are as follows:
- Create two variables “hurdle” and “level” to count the hurdles that Kevin has jumped and to count the level cleared, respectively.
- Iterate till the ”hurdle” becomes greater than ‘N’.
- “hurdle” = “hurdle” + “level” + 1
- “level” = “level” + 1
- Return “level” - 1
The basic idea of this approach is to generate a mathematical equation to solve this problem. Hurdles at a particular level are increased by 1 as compared to their previous level and so,
we can say 1 + 2 + 3 + 4 + … up to level ‘k’ <= ‘N’, where ‘k’ is the maximum level that Kevin can clear after jumping ‘N’ hurdles.
Therefore, ‘k’ * (‘k’ + 1) <= 2* ‘N’ {Sum of Arithmetic Progression}
(‘k’^2 + ‘k’) <= 2 * ‘N’
For the given inequality, we want to find the maximum value of ‘k’ which satisfies it.
Consider, the above equation as a polynomial equation and then find its larger root i.e.
‘k’ = ( -1 + sqrt (1 + 4*2*’N’) ) / 2 by using the sridharacharya formula.
Now, the solution to our problem will be the largest integer less than or equal to the root.
The steps are as follows:
- Take the floor of sqrt( 1 + 4*2*’N’) and store in some variable say, ‘k’.
- Return (-1 + k) / 2