I am doing an assessment that is asking by the given "n" as input which is a length of a stick; how many triangles can you make? (3 < n < 1,000,000)

For example:

```
input: N=8
output: 1
explanation:
(3,3,2)
input: N=12
output: 3
explanation:
(4,4,4) (4,5,3) (5,5,2)
```

Now the codes I wrote are returning 33 % accuracy as the web assessment is throwing time limit error.

```
ans = 0
n = int(input())
for a in range(1, n + 1):
for b in range(a, n - a + 1):
c = n - a - b
if a + b > c >= b:
ans += 1
print(ans)
```

code b:

```
ans = 0
n = int(input())
for i in range(1,n):
for j in range(i,n):
for c in range(j,n):
if(i+j+c==n and i+j>c):
ans+=1
print(ans)
```

How can this be made faster?

·
Santiago Trujillo

Alcuin's sequence [See: https://en.wikipedia.org/wiki/Alcuin%27s_sequence] is a series expansion of the polynomial below, where the *n*th coefficient corresponds to the *n*th answer, that is, the maximum amount of unique integer triangles with perimeter `n`

.

The algorithmic implementation of this is simply a formula. The Online Encyclopaedia of Integer Sequences (OEIS) provides many formulas that achieve this, the simplest of which is:

`round(n^2 / 48)`

(Even)`round((n+3)^2 / 48)`

(Odd)

[See: https://oeis.org/A005044]

This evidently has a constant time complexity, given that the only functions required are modulo 2, integer squared and round, each of which are constant time (under certain definitions).

Expanded:

```
def triangles(n):
if n % 2 == 0:
return round(n ** 2 / 48)
else:
return round((n + 3) ** 2 / 48)
```

1-Liner:

```
def triangles(n): return round(n ** 2 / 48) if n%2==0 else round((n + 3) ** 2 / 48)
```

Or even:

```
def triangles(n): return round((n + 3 * n%2) ** 2 / 48)
```

No `import`

s are needed.

As the OP questioned, why do we divide by 48? While I can't answer that explicitly, let's get an intuitive understanding. We are squaring numbers, so it is evidently going to expand greatly. By the time we get to 5, that would give 64 (8^2). So, there must be a constant (albeit a reciprocal) to restrict the growth of the parabola, thus the / 48.

When we graph the OP's method, it gives an alternating parabola. This explains why there is a back-and-forth with the +3 and +0.

·
Santiago Trujillo
Report

This is an intuitive O(n) algorithm I came up with:

```
def main():
n = int(input())
if n < 3:
print(0)
return
ans = n % 2
for a in range(2, n//2+1):
diff = n - a
if diff // 2 < a:
break
if diff % 2 == 0:
b = diff // 2
else:
b = diff // 2 + 1
b = max(b - a // 2, a)
c = n - b - a
if abs(b - c) >= a:
b += 1
c -= 1
ans += abs(b-c)//2 + 1
print(ans)
main()
```

I find the upper bound and lower bound for `b`

and `c`

and count the values in that range.

·
Santiago Trujillo
Report

I thought of a completely different way to do it:

We take the smallest side and call it

`a`

. It can never be more than`n/3`

, otherwise a different side would be the smallest.We try to figure out what is the next smallest side (

`b`

):- We see what's left after reducing our
`a`

. - We divide it by 2 in order to find the middle where we'll start advancing from
- We'll see how far we can get before the difference between the lengths is
`a`

(or the difference from the middle is`a/2`

) as that's the minimum`b`

side length that is possible and satisfies`a+b>c`

. Basically, the second smallest side is`a/2`

less than the middle. - The smallest side is the maximum between our calculation or
`a`

, in case`b==a`

.`b`

can never be lower than`a`

as it violates our first rule that`a`

is the smallest.

- We see what's left after reducing our
We figure out the difference from the middle and the smallest side. That's how many possible solutions we have for the other 2 sides.

Add everything together for every

`a`

and that's our solution.

The `floor`

, `ceil`

and `%`

are fixes for when `a`

is odd, the middle is `.5`

, or `+1`

in case `b+c`

is even, cause `b==c`

is then possible.

Code:

```
import math
n = int(input("Enter a number: "))
total = 0
# a is the shortest side
for a in range(1, (n//3)+1):
length_left = n-a
middle_number = length_left/2
# Shortest potential side b where the distance between b and c is smaller than a (c-b < a)
b = middle_number-(math.ceil(a/2)-1)-((length_left % 2)/2)
# We calculate how far it is from the middle
max_distance_from_middle = middle_number - max(b, a)
# Add another 1 if the length is even, in case b==c
adding = math.floor(max_distance_from_middle) + (1 if length_left % 2 == 0 else 0)
total += adding
print(total)
```

Or in an ugly one-liner:

```
n = int(input("Enter a number: "))
print(sum(math.floor((n-a)/2 - max((n-a)/2 - math.ceil(a/2) + 1 - (((n-a) % 2)/2), a)) + 1 - ((n-a) % 2) for a in range(1, (n//3)+1)))
```

·
Santiago Trujillo
Report