Ninja And The Triangle
Ninja has been given ‘N’ stars. Ninja has to make a triangle using these stars. The ‘i’th’ level of a triangle contains a ‘i’ number of stars.

Can you help Ninja to make a triangle as large as possible using these stars?

For example:

Let the number of stars is 6.

Then we can make a triangle of maximum height 3.

Note:

If the number of stars is 7 in the above example, then also the maximum height of the triangle is 3. This is because to make a triangle of height 4 we need at least 10 stars. So in this case (N = 7) to we will return 3.

Input Format

The first line of input contains an integer 'T' which denotes the number of test cases or queries to be run. Then the test cases follow. The first and only line of each test case contains a single integer ‘N’ representing the number of stars.

Output Format :

For each test case, print the maximum height of the triangle we can make with the given number of stars. Print the output of each test case in a separate line.

Note:

You do not need to print anything; it has already been taken care of. Just implement the given function.

Constraints:

1

Question

Ninja And The Triangle

Ninja has been given ‘N’ stars. Ninja has to make a triangle using these stars. The ‘i’th’ level of a triangle contains a ‘i’ number of stars.

Can you help Ninja to make a triangle as large as possible using these stars?

For example:

Let the number of stars is 6.

Then we can make a triangle of maximum height 3.

Note:

If the number of stars is 7 in the above example, then also the maximum height of the triangle is 3. This is because to make a triangle of height 4 we need at least 10 stars. So in this case (N = 7) to we will return 3.

Input Format

The first line of input contains an integer 'T' which denotes the number of test cases or queries to be run. Then the test cases follow.

The first and only line of each test case contains a single integer ‘N’ representing the number of stars.

Output Format :

For each test case, print the maximum height of the triangle we can make with the given number of stars.

Print the output of each test case in a separate line.

Note:

You do not need to print anything; it has already been taken care of. Just implement the given function.

Constraints:

1 <= ‘T’ <= 100
1 <= ‘N’ <= 10 ^ 8

Where ‘T’ denotes the total number of test cases and ‘N’ represents the number of stars.

Time Limit: 1 second

Accepted Answer

Brute Force

We know that the ‘i’th’ level of a triangle contains ‘i’ number of stars. So we can start making the triangle from top to bottom. If we have enough stars, then we make the next level of the triangle. Otherwise, we stop and return the number levels made so far.

Here is the algorithm:

We declare a variable ‘maxHeight’ and ‘numberOfStars’ in which we store the maximum height of the triangle that we can make and the number of stars used so far in making the triangle.
We run a loop while ‘numberOfStars’ less than ‘N’:
- ‘maxHeight’++.
- ‘numberOfStars’ += ‘maxHeight’.
If ‘numberOfStars’ == ‘N’:
- Return ‘maxHeight’.
Else:
- Return ‘maxHeight’ - 1.

Space Complexity: O(1)Explanation:

O(1).

We are not using any extra space for finding our resultant answer. Hence, the overall space complexity is O(1).

Time Complexity: OtherExplanation:

O(sqrt(N)) where ‘N’ represents the number of stars.

For making a triangle from top to bottom at every ‘i’th’ level we use ‘i’ stars.

For example :

For making 1s’t level we use 1 star.

For making 2n’d level we use 2 stars.

For making the ‘K’th’ level, we use ‘K’ stars.

So, the total number of stars used till the ‘K’th’ level is 1 + 2 + 3 + … + K.

N = (K * (K + 1)) / 2

=> N = K ^ 2

=> K = sqrt(N).

Hence the time complexity is O(sqrt(N)).

C++ (g++ 5.4)

/*



	Time complexity: O(sqrt(N))

	Space complexity: O(1) 



	where N represents the number of stars.



*/



int ninjaAndTriangle(int n) 

{

	int maxheight = 1;

	int numberOfStars = 1;

	

    // Iterate till numberOfStars is less than n 

	while (numberOfStars < n) 

    {

		maxheight++;

		numberOfStars += maxheight;

	}

    

	// Check if numberOfStars is equal to n

	if (numberOfStars == n) 

    {

		return maxheight;

	} 

    else 

    {

		return maxheight - 1;

	}

}

Python (3.5)

'''



	Time complexity: O(sqrt(N))

	Space complexity: O(1) 



	where N represents the number of stars.



'''



def ninjaAndTriangle(n):



    maxheight = 1

    numberOfStars = 1



    # Iterate till numberOfStars is less than n 

    while (numberOfStars < n):

		

        maxheight += 1

        numberOfStars += maxheight



    # Check if numberOfStars is equal to n

    if (numberOfStars == n):

        return maxheight



    else:

        return maxheight - 1

Java (SE 1.8)

/*



	Time complexity: O(sqrt(N))

	Space complexity: O(1) 



	where N represents the number of stars.



*/



public class Solution 

{

	public static int ninjaAndTriangle(int n) 

    {

		int maxheight = 1;

		int numberOfStars = 1;

		

        // Iterate till numberOfStars is less than n 

		while (numberOfStars < n) 

        {

			maxheight++;

			numberOfStars += maxheight;

		}

		

        // Check if numberOfStars is equal to n

		if (numberOfStars == n) 

        {

			return maxheight;

		} 

        else 

        {

			return maxheight - 1;

		}

	}

}

Accepted Answer

Mathematics

As we know the ‘i’th’ level of a triangle contains ‘i’ number of stars. So let’s assume by using ‘N’ stars we can make a triangle of at most ‘K’ height.

We can write this in the following manner:

1 + 2 + 3 + … + K <= N

=> (K * (K + 1)) / 2 <= N

=> K ^ 2 + K - 2 * N <= 0

This is a quadratic equation. Now we have to find the root of this quadratic equation.

If ax^2 + bx + c = 0 is a quadratic equation, then the value of x is given by the following formula:

Our quadratic equation is K ^ 2 + K - 2 * N <= 0.

So K = (-1 + sqrt(1 - (4 * 1 * (-2)*N))) / 2 and (-1 - sqrt(1 - (4 * 1 * (-2)*N))) / 2.

We neglect the negative root because ‘K’ can’t be negative.

So, K = (-1 + sqrt(1 + 8 * N) ) / 2.

We simply apply the above formula and return our answer.

Space Complexity: O(1)Explanation:

O(1).

We are not using any extra space for finding our resultant answer. Hence the overall space complexity is O(1).

Time Complexity: O(1)Explanation:

O(1).

We are only applying the formula for finding our answer. Hence, the overall time complexity is O(1).

Java (SE 1.8)

/*



	Time complexity: O(1)

	Space complexity: O(1) 



*/



public class Solution 

{

	public static int ninjaAndTriangle(int n) 

    {	

        // Use formula to find the solution

		int maxHeight = (-1 + (int) Math.sqrt(8 * n + 1)) / 2;

		

        return maxHeight;

	}

}

Python (3.5)

'''



	Time complexity: O(1)

	Space complexity: O(1) 



'''



from math import sqrt



def ninjaAndTriangle(n):

	

	# Use formula to find the solution

	maxHeight = (-1 + int(sqrt(8 * n + 1))) // 2

	

	return maxHeight

C++ (g++ 5.4)

/*



	Time complexity: O(1)

	Space complexity: O(1) 



*/



#include 



int ninjaAndTriangle(int n) 

{

	// Use formula to find the solution

	int maxHeight = (-1 + (int)sqrt(8 * n + 1)) / 2;

	

    return maxHeight;

}

Ninja has been given ‘N’ stars. Ninja has to make a triangle using these stars. The ‘i’th’ level of a triangle contains a ‘i’ number of stars.

Can you help Ninja to make a triangle as large as possible using these stars?

For example:

Note:

Input Format

Output Format :

Note:

Constraints:

Top Blackrock Software Developer interview questions & answers

Popular interview questions of Software Developer

Top HR questions asked in Blackrock Software Developer