Ninja And The Triangle

Easy
0/40
Average time to solve is 15m
profile
Contributed by
44 upvotes
Asked in companies
WalmartBlackrock

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
2
5
Sample Output 1:
1
2
Explanation for Sample Output 1:
For sample test case 1: 


In this example, we can make a triangle of height 1 only. For making a triangle of height 2, we need at least 3 stars but we have only 2 stars.

For sample test case 2: 


In this example, we can make a triangle of height 2 only. For making a triangle of height 3, we need at least 6 stars but we have only 5 stars.
Sample Input 2:
2
6
10
Sample Output 2:
3
4
Explanation for Sample Output 2:
For sample test case 1: 


In this example, we can make a triangle of height 3.

For sample test case 2:


In this example, we can make a triangle of height 4.
Hint

Think of the Brute-Force approach.

Approaches (2)
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:

  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.
Time Complexity

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

Space Complexity

O(1).

 

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

Code Solution
(100% EXP penalty)
Ninja And The Triangle
Full screen
Console