Ninja And The Triangle

Posted: 9 Mar, 2021
Difficulty: Easy

PROBLEM STATEMENT

Try Problem

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
Approach 1

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:

  1. 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.
  2. We run a loop while ‘numberOfStars’ less than ‘N’:
    • ‘maxHeight’++.
    • ‘numberOfStars’ += ‘maxHeight’.
  3. If ‘numberOfStars’ == ‘N’:
    • Return ‘maxHeight’.
  4. Else:
    • Return ‘maxHeight’ - 1.
Try Problem