Сколько способов представить число, как сумму трех разных чисел (строго O(n))

Question

Нужно посчитать сколько есть способов представить число, как сумму трех разных чисел. Например число 8 можно представить двумя способами: 1 + 2 + 5 и 1 + 3 + 4. А число 6 одним: 1+2+3. Решение должно быть O(n). Мне пока удалось только посчитать количество способов, где два из трех слагаемых могут быть одинаковым. А вот как провести условие, чтоб все три были разные, не могу понять.

def count(n):
  counter = 0

  if n < 6: 
    return counter
  else:
    counter = (n - 1) * (n - 2) / 2

  return counter


if __name__ == "__main__":
    print(count(6)) #1 
    print(count(8)) # 2
    print(count(30)) # 61
    print(count(1337)) # 148296

Answer 1

Легче посчитать количество плохих и вычесть из общего. Количество троек, где двое равны - можно посчитать за O(n)(можно и быстрее)(просто перебирать повторяющийся элемент). Количество троек, где равны может быть не больше 1(n либо делится на 3,либо нет). Количество троек всего равно C(n + 2, 2)

Answer 2

А обязательно за O(n)? За O(1) можно?

n = int(input())

j = n//6
k = n % 6
if k == 0:
    j = j - 1
    k = 6

n = (3*j+k-3)*j
if k == 6: n = n+1

print(n)

Вроде бы так, если поверить вот этому материалу

Можно еще посмотреть на эту последовательность и эту

Нет, конечно, я могу вклеить сюда цикл и получить O(n)... :-)

БЛОГ НА HUSL

Сколько способов представить число, как сумму трех разных чисел (строго O(n))

Ответы (2 шт):