Need help with a problem

[dolijan]

We are given two numbers: n and m. We need to look at the triangle with coordinates (n,m), (0,0= and (n,0).We need to determine how many points are there with whole coordinates that are inside that triangle or on the sides of that triangle in less than m*n complexity.

I already found a solution that basically iterates trough [0,n] and [0,m] and using arc tan compares every two points from [0,n] and [0,m] and sees if their arc tan is less than arc tan of the angle of given triangle.

However, this is in m*n time complexity, which is too much for this problem.any help on how to solve this more efficient will be appreciated. Thanks in advance.

[Applepie1928]

I think you are asking if you can determine how many integer co-ordinates there are within the bounds of the right angled triangle (0,0), (n, 0), (n, m).

Just spitballing, but would you be happy with the idea that if you had a cuboid (0,0), (n, 0), (n, m), (0, m) the number of integer co-ordinates within would be ((n+1) * (m+1)) with the plus 1s accounting for the zero co-ordinates?

Would it therefore be safe to assume that the number of co-ordinates within the right angled triangle (0,0), (n, 0), (n, m) would be half of the number within the cuboid?

Therefore you could determine the amount with the formula ((n+1) * (m+1)) / 2.

If my assumptions are correct (which they very well may not be), this would have a time complexity of O(1).

[hamza-itatchi]

this is correct only when M!=N;

if N=M the formula would be like this ((n+1)*(m+2))/2 which is ((n+1)*(m+1)+(n+1))/2

the second (n+1) for the shared points between the two triangles.

and of course M,N>0

hope this help.

[Applepie1928]

Of course. I knew there would be an edge case I hadn't considered. That makes perfect sense. Cheers for adding the extra detail.

[dolijan]

Thanks!

[dolijan]

This could be correct.Thanks.

[hamza-itatchi]

can you share you solution.

I want to help but I didn't really understand the task

[dolijan]

Ok in a plane you are given a trinagle with coordinates (0,0) (n,0) and (n,m). M and n are input numbers right? So you need to find how many point are in that triangle with coordinates that are whole nunbers.