Kiểm tra mảng có thể sắp xếp thỏa mãn điều kiện nums[2*i+1] = 2*nums[2*i] trong Python

Cho mảng nums. Kiểm tra có thể sắp xếp lại sao cho với mọi i, phần tử tại chỉ số lẻ 2*i+1 gấp đôi phần tử tại chỉ số chẵn 2*i.

Ví dụ: [8, -4, 4, -8] → sắp xếp [-4, -8, 4, 8] → i=0: -8 = 2*(-4), i=1: 8 = 2*4 → True.

Thuật toán

• Đếm tần suất các giá trị.
• Duyệt các giá trị theo thứ tự giá trị tuyệt đối tăng dần.
• Với mỗi giá trị x còn dư, cần tìm 2*x cũng còn dư. Giảm tần suất cả hai.
• Nếu không tìm thấy 2*x → False.

Triển khai

from collections import defaultdict

def solve(nums):
    freq = defaultdict(int)
    for v in nums:
        freq[v] += 1
    for v in sorted(nums, key=abs):
        if freq[v] == 0:
            continue
        if freq[2 * v] == 0:
            return False
        freq[v] -= 1
        freq[2 * v] -= 1
    return True

nums = [8, -4, 4, -8]
print(solve(nums))  # True

Đầu vào / Đầu ra

Input: [8, -4, 4, -8]
Output: True

Lưu ý: Sắp xếp theo abs đảm bảo xử lý số âm trước (ví dụ -4 cần -8, không phải 4 cần 8).