Clumsy Factorial ใน Python

Clumsy Factorial คือ factorial ที่สลับการดำเนินการ: ×, ÷, +, - ซ้ำกัน โดยยังคงลำดับความสำคัญของการดำเนินการ (×,÷ ก่อน +,-)

ตัวอย่าง

clumsy(10) = 10 × 9 ÷ 8 + 7 − 6 × 5 ÷ 4 + 3 − 2 × 1 = 12

อัลกอริทึม: Stack Simulation

1. ใช้ stack เก็บตัวเลขที่จะบวก/ลบในท้ายที่สุด
2. × และ ÷ คำนวณทันทีกับ top ของ stack
3. + push ตัวเลขเข้า stack, - push ตัวเลขลบเข้า stack
4. ท้ายสุด sum ทั้ง stack

ตัวอย่างโค้ด Python

class Solution(object):
    def clumsy(self, N):
        operations = ["*", "/", "+", "-"]
        stack = [N]
        op_index = 0
        N -= 1
        
        while N > 0:
            op = operations[op_index]
            
            if op == "*":
                # จัดการเครื่องหมาย
                if stack[-1] >= 0:
                    stack[-1] *= N
                else:
                    stack[-1] = -1 * (abs(stack[-1]) * N)
            elif op == "/":
                if stack[-1] >= 0:
                    stack[-1] //= N   # floor division
                else:
                    stack[-1] = -1 * (abs(stack[-1]) // N)
            elif op == "+":
                stack.append(N)
            else:  # "-"
                stack.append(-N)
            
            op_index = (op_index + 1) % 4
            N -= 1
        
        return sum(stack)

# ทดสอบ
ob = Solution()
print(ob.clumsy(10))  # Output: 12

ตัวอย่าง Input/Output

Input: 10
Output: 12

ความซับซ้อน: Time O(N), Space O(N)