You are given a number N that represents the number of coins you have and you have to print the maximum possible height H of triangle which can be made from these coins in such a way that i^{th} row of the triangle contains i coins.
QUICK EXPLANATION:
Maximum possible height of the triangle is the maximum possible value of H such that \frac{H\times(H+1)}{2} \le N.
EXPLANATION:
It should be noted that i^{th} row of triangle contains i coins. Therefore, a traingle with H height will contain 1 coin in 1^{st} row, 2 coins in 2^{nd} row, … , H coins in H^{th} row and total number of coins required to build a triangle of height H will be equal to
As we are asked to find the maximum possible height of the triangle, we have to find the maximum value of H such that \frac{H \times (H+1)}{2} \le N. Note that the value of N ~= 10^9 in worst case and therefore the maximum possible value of H will be order of \sqrt{N}.
We can use following simple procedure to solve this problem.
int sum(int h) {
return (h * (h+1) / 2);
}
void solve() {
int n;
cin >> n;
int h = 1;
while(sum(h) <= n) {
h ++;
}
cout << h - 1 << "\n";
}
TIME COMPLEXITY:
O(\sqrt{N})
BONUS:
Try solving same problem with 1 \le N \le 10^{15}.
AUTHOR’S AND TESTER’S SOLUTION:
Author’s solution can be found here.
Tester’s solution can be found here.
The O(1) Solution Can Be Explained Like This :
You Can See That For Height = 1 , Number of Coins Needed =1
For Height=2,total Coins Needed=3;
for height=3,total coins needed=6
for height 4,total coins needed =10
for height 5,total coins needed=15
if u observe the pattern : (1,3,6,10,15…)
its = (1,1+2,1+2+3,1+2+3+4,1+2+3+4+5,…)
whhich has a simple formula : summation of first n natural numbers = n*(n+1)/2
therefore , height(height+1)/2 <= no of gold coins;
solving this , we get the ans as : (-1+sqrt(1+8*goldcoins))/2
Reason is 8*noofgoldcoins will overflow for integer. Hence give a negative number or some random value inside square root. That is why, I used 8.0 to convert value to double whose range is more than int and it passes both subtask.
By using the formula for roots
If the equation is ax^2 + bx + c = 0
it implies
x = ( -b + sqrt( b^2 - 4ac ) ) / 2 or ( -b - sqrt( b^2 - 4ac ) ) / 2
And since the height can’t be negative we ditch the second one.
first of all you have to change the data type of the variables.
when you change your data type to the following your code will get partially correct.
long int ctr=0,j,N;
long long int sum=0;
but you will not get the complete AC from this code , bcz for higher values of N it will get TLE as we are using for loop which is increasing the time complexity.