Như ta biết, giai thừa của số nguyên dương n là tích tất cả số nguyên dương ≤ n. Vậy factorial(10) = 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1. Ta sẽ tìm giai thừa cẩu thả: dùng số theo thứ tự giảm, thay phép nhân bằng chu kỳ cố định: nhân (*), chia (/), cộng (+), trừ (-) theo thứ tự đó.
Giai thừa cẩu thả như clumsy(10) = 10 * 9 / 8 + 7 - 6 * 5 / 4 + 3 - 2 * 1. Tuy nhiên, các phép toán vẫn áp dụng theo thứ tự ưu tiên toán học: thực hiện tất cả nhân chia trước cộng trừ, nhân chia xử lý trái sang phải. Phép chia là chia lấy phần nguyên (floor division) nên 10 * 9 / 8 = 11. Điều này đảm bảo kết quả là số nguyên.
Ví dụ, đầu vào 10, kết quả 12, vì 12 = 10 * 9 / 8 + 7 - 6 * 5 / 4 + 3 - 2 * 1.
Để giải quyết, ta làm theo các bước −
- định nghĩa mảng operations chứa [* / + -], tạo stack rỗng, push N vào stack
- index := 0
- giảm N 1
- khi N khác 0:
- nếu operations[index] = *, thì
- nếu stack[-1] >= 0, cập nhật stack[-1] = N * stack[-1]
- ngược lại stack[-1] = -1 * |N * stack[-1]|
- ngược lại nếu operations[index] = /, thì
- nếu stack[-1] >= 0, cập nhật stack[-1] = stack[-1] // N
- ngược lại stack[-1] = -1 * |stack[-1] // N|
- ngược lại nếu operations[index] = +, push N vào stack
- ngược lại push (-1 * N) vào stack
- index := (index + 1) mod độ dài operations
- giảm N 1
- nếu operations[index] = *, thì
- trả về tổng các phần tử stack.
Xem triển khai sau −
Ví dụ
class Solution(object): def clumsy(self, N): operations = ["*","/","+","-"] stack = [] index = 0 stack.append(N) N-=1 while N: if operations[index] == "*": if stack[-1]>=0: stack[-1] *=N else: stack[-1] = -1*(abs(stack[-1])*N) elif operations[index] == "/": if stack[-1]>=0: stack[-1] //=N else: stack[-1] = -1*(abs(stack[-1])//N) elif operations[index] == "+": stack.append(N) else: stack.append(-1*N) index = (index+1) % len(operations) N-=1 return sum(stack) ob = Solution() print(ob.clumsy(10))
Đầu vào
10
Kết quả
12