Problem

Submissions

Hints & solutions

Discuss

Hurdle Game

Easy

0/40

Average time to solve is 10m

Contributed by

2 upvotes

Asked in companies

Problem statement

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).

Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1 :

2
6
11

Sample Output 1 :

3
4

Explanation of sample input 1 :

In the first test case, Kevin has cleared level 1, level 2, and level 3.

In the second test case, Kevin has cleared level 1, level 2, level 3, and level 4.

Sample Input 2 :

2
1
0

Sample Output 2 :

1
0

Explanation of sample input 2 :

In the first test case, Kevin has only cleared level 1.

In the second test case, Kevin has not cleared any of the levels.

Hint 1

Hint 2

Can you get the answer by using a loop?

Approaches (2)

Approach 1

Approach 2

Brute Force

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

Time Complexity

O(sqrt(N)), where ‘N’ is the total number of hurdles that Kevin has jumped.

Since at each level, hurdles get increased by 1 as compared to their previous level and, so the overall time complexity will be O(sqrt(N)).

Space Complexity

O(1)

Since we are not using any extra space, the overall space complexity will be O(1).

(100% EXP penalty)

Hurdle Game

Console