задача с литкода №1006

Question

Факториал положительного целого числа — это произведение всех положительных целых чисел, меньших или равных .nn

Например, factorial(10) = 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1. Мы делаем неуклюжий факториал , используя целые числа в порядке убывания, заменяя операции умножения на фиксированную ротацию операций с умножением '*', делением '/', сложением '+'и вычитанием '-'в этом порядке.

Например, clumsy(10) = 10 * 9 / 8 + 7 - 6 * 5 / 4 + 3 - 2 * 1. Однако эти операции по-прежнему применяются с использованием обычного порядка арифметических операций. Мы выполняем все шаги умножения и деления перед любыми шагами сложения или вычитания, а шаги умножения и деления выполняются слева направо.

Кроме того, мы используем разделение по этажам, такое, что 10 * 9 / 8 = 90 / 8 = 11.

Учитывая целое число n, верните неуклюжий факториал числаn .

Пример 1:

Вход: n = 4 Выход: 7 Объяснение: 7 = 4 * 3/2 + 1 Пример 2:

Вход: n = 10 Выход: 12 Объяснение: 12 = 10 * 9 / 8 + 7 — 6 * 5 / 4 + 3 — 2 * 1

Ограничения:

1 <= n <= 104

вот код

class Solution:

    def clumsy(self, n: int) -> int:
        h = 0
        d = n
        j=n//4
        for i in range(n-1):
            if h==0:
                d*=(n-i-1)
            elif h==1:
                d//=(n-i-1)
            elif h==3:
                h=-1
            h+=1
        d+=j
        return d

ломается после семи

Answer 1

Разобьём сумму на части, начало и хвост удобнее вычислить отдельно:

def clumsy(n: int) -> int:
    mod = n%4
    res = 0
    for t  in range(mod + 4, n-4+1, 4):
        res -= t*(t-1)//(t-2) - t+3
    if n > 3:
        return res + n*(n-1)//(n-2) + n-3 + [0, -1,-2,-6][mod]
    else:
        return [0, 1, 2, 6][mod]

Однако, посмотрев на закономерности:

def clumsy(n: int) -> int:
    return n + ((n//3)*3 if n<=4 else [1,2,2,-1][n&3])

БЛОГ НА HUSL

задача с литкода №1006

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