Kiểm tra quay về 12h bằng cách cộng/trừ giây cho trước (Python)

Bài toán: Cho mảng seconds các giá trị giây. Từ 12h (0 giây), mỗi giá trị có thể cộng hoặc trừ. Kiểm tra có thể quay về 12h (bội số của 86400 giây = 24h) không.

Thuật toán Bitmask

Mỗi giây có 2 lựa chọn: + hoặc -. Với n giá trị, có 2^n tổ hợp. Duyệt tất cả bằng bitmask.

Triển khai Python

def solve(seconds):
    n = len(seconds)
    for mask in range(1 << n):  # 2^n combinations
        total = 0
        for j in range(n):
            if mask & (1 << j):
                total += seconds[j]
            else:
                total -= seconds[j]
        if total % (24 * 60 * 60) == 0:  # 86400 seconds = 24h
            return True
    return False

# Test
print(solve([40, 90, 50]))   # True: +40 -90 +50 = 0
print(solve([3600, 3600]))   # True: +3600 -3600 = 0
print(solve([100]))          # False: ±100 không chia hết 86400

Kết quả

True

Giải thích

• Duyệt mask từ 0 đến 2^n - 1. Bit j = 1 → cộng, 0 → trừ.
• Kiểm tra tổng có chia hết cho 86400 (số giây trong 24h) không.
• Độ phức tạp: O(n × 2^n). Chỉ phù hợp n ≤ 20.
• Có thể tối ưu bằng DP subset sum (modulo 86400) cho n lớn hơn.