In an isosceles triangle that has exactly two equal sides, the equal sides are called legs and the third side is called the base. But in this question they assumed that the same sides are the ones called base. Please get your facts right before posting up a problem. Lost my confidence for an hour.
Hey, considering x base and when I try to draw a triangle for x, the number of squares fit is always more than the expected output.
For example: base = 9
The total number of 2x2 squares fit is 10 but the answer is 6, how?
How did you get 10 squares for base=10?
I think you simply divided the area of the triangle by the area of 1 square.
(int)((99)/2)/(22) = 10
This method does not work because there will be many empty spots(these spots would be isosceles right angled triangles of base=1) in the triangle when filling it with squares. When you use the area method it gives extra squares because two such empty spots would have an area of the required square but according to the question this is an invalid count, as you would can’t cut up the squares.
Hope you understood the explanation.
There is slight improvement I would like to add:-
Since there are (b/2 -1) in base, we have total of 2*(b/2 -1) - 1 blocks and then recurse for F(b-4).
So, it will be:-
int F(b)
{
if(b<=3)
return 0;
return 2*(b/2 - 1) -1 + F(b-4);
}
amazing man!
mildly incorrect explanation given,the sum should be
(b/2-1)+(b/2-2)…
and formula for sum of integers upto n is
n(n+1)/2 so it would be
(m(m+1)/2)-m=m(m-1)/2
same final result but this would be the correct way to reach the result
Your Explanation was very clear and had really helped me understand the concept
Hey, your approach is much simpler but when you are scaling it from 1x1 to 2x2 you are dividing the count with 2 . we need to prove this step
#include <bits/stdc++.h>
using namespace std;
int triangle(int data)
{int sum=0;
if(data>1)
{
sum=(data/2-1)+triangle(data-2);
return sum;
}
else return 0;
}
int main()
{
int test;
cin>>test;
while(test–)
{
int data;
cin>>data;
if(data>2){
int result=triangle(data);
cout<<result<<endl;
}
else cout<<“0”<<endl;
}
return 0;
}
// use the simplest way to solve this problem .
// and let me know if you have any doubt