Hurdle Game
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

Question

Hurdle Game

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

Accepted Answer

The task is to determine the number of levels cleared by Kevin based on the total number of hurdles he has jumped.

Each level 'i' has 'i' hurdles, so Kevin can only reach level 'i' if he has cleared level 'i-1'.
Count the number of levels cleared by dividing the total number of hurdles by the sum of the first 'n' natural numbers.
The formula to calculate the sum of the first 'n' natural numbers is (n * (n + 1)) / 2.

Accepted Answer

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

Space Complexity: O(1)Explanation:

O(1)

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

Time Complexity: OtherExplanation:

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

Java (SE 1.8)

/*

	Time complexity: O(sqrt(N)) 

	Space complexity: O(1)

	

	Where 'N' is the total number of hurdles that Kevin has jumped.

*/



public class Solution {

    public static int levelCleared(int n) {

        // Variables to store hurdles that Kevin has jumped and the level that he has cleared.

        int hurdle = 0, level = 0;



        // Iterate till "hurdle" becomes greater than 'n'.

        while (hurdle <= n) {

            // Increment "hurdle" by number of hurdles at level - ("level" + 1).

            hurdle = hurdle + level + 1;



            // Increment the "level" by 1.

            level = level + 1;

        }



        return level - 1;

    }

}

Python (3.5)

"""

	Time complexity: O(sqrt(N)) 

	Space complexity: O(1)

	

	Where N is the total number of hurdles that Kevin has jumped.

"""





def levelCleared(n):

    #  Variables to store hurdles that Kevin has jumped and the level that he has cleared.

    hurdle, level = 0, 0



    #  Iterate till "hurdle" becomes greater than 'n'.

    while hurdle <= n:

        #  Increment "hurdle" by number of hurdles at level - ("level" + 1).

        hurdle = hurdle + level + 1



        #  Increment the "level" by 1.

        level = level + 1



    return level - 1

C++ (g++ 5.4)

/*

	Time complexity: O(sqrt(N)) 

	Space complexity: O(1)

	

	Where N is the total number of hurdles that Kevin has jumped.

*/



int levelCleared(int n)

{

    //  Variables to store hurdles that Kevin has jumped and the level that he has cleared.

    int hurdle = 0, level = 0;



    //  Iterate till "hurdle" becomes greater than 'n'.

    while (hurdle <= n)

    {

        //  Increment "hurdle" by number of hurdles at level - ("level" + 1).

        hurdle = hurdle + level + 1;



        //  Increment the "level" by 1.

        level = level + 1;

    }



    return level - 1;

}

Accepted Answer

Mathematics

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

Space Complexity: O(1)Explanation:

O(1)

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

Time Complexity: O(logn)Explanation:

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

Since we are using the inbuilt “sqrt” function which takes time O(log(N)) and so, the overall time complexity will be O(log(N)).

Python (3.5)

"""

	Time complexity: O(log(N))

	Space complexity: O(1)

	

	Where N is the total number of hurdles that Kevin has jumped.

"""



import math





def levelCleared(n):



    #  Returns the maximum possible level that Kevin has cleared.

    return int((-1 + math.sqrt(1 + 4 * 2 * n)) // 2)

Java (SE 1.8)

/*

	Time complexity: O(log(N))

	Space complexity: O(1)

	

	Where 'N' is the total number of hurdles that Kevin has jumped.

*/



public class Solution {

    public static int levelCleared(int n) {

        // Returns the maximum possible level that Kevin has cleared.

        return (-1 + (int) Math.sqrt(1 + 4 * 2 * n)) / 2;

    }

}

C++ (g++ 5.4)

/*

	Time complexity: O(log(N))

	Space complexity: O(1)

	

	Where N is the total number of hurdles that Kevin has jumped.

*/



int levelCleared(int n)

{

    //  Returns the maximum possible level that Kevin has cleared.

    return (-1 + sqrt(1 + 4 * 2 * n)) / 2;

}

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 :

Input Format :

Output Format :

Note :

Constraints :

Top Rupeek Software Developer interview questions & answers

Popular interview questions of Software Developer

Top HR questions asked in Rupeek Software Developer