Kiểm tra nửa mảng có thể giảm về 0 bằng phép toán lặp trong Python

Cho mảng số nguyên dương và số m. Mỗi bước: chọn một số phần tử giảm 1, các phần tử còn lại tăng m. Kiểm tra có thể làm ≥ nửa phần tử bằng 0 sau vài bước không.

Ví dụ: [10,18,35,5,12], m=4 → True.

Quan sát toán học

Sau mỗi bước, giá trị modulo (m+1) của mỗi phần tử không đổi. Do đó, nhóm các phần tử theo val % (m+1). Nếu có nhóm nào kích thước ≥ n/2 → có thể đưa nhóm đó về 0.

Triển khai

def solve(arr, m):
    freq = [0] * (m + 1)
    for v in arr:
        freq[v % (m + 1)] += 1
    for cnt in freq:
        if cnt >= len(arr) / 2:
            return True
    return False

arr = [10, 18, 35, 5, 12]
print(solve(arr, 4))  # True

Đầu vào / Đầu ra

Input: [10, 18, 35, 5, 12], 4
Output: True

Giải thích: Phép toán保持 modulo (m+1) bất biến. Chỉ cần tìm modulo class chiếm ≥ nửa mảng.