Last Updated: 9 Mar, 2021
Ninja And The Triangle
Easy
Asked in companies
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
Approaches
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.
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.