Question

Cho dãy A gồm N số nguyên: a1,a2,...,an.Hãy cho biết có bao nhiêu số chia hết cho 3 trong dãy A đã cho. a) Hãy xá định dữ liệu vào (Input) và dữ liệu ra (output) bài toán trên. b) Viết thuật toán để giải bài toán trên.

Answer 1

def count_pairs_divisible_by_3(arr):
    n = len(arr)
    
    # Đếm số lượng số dư khi chia cho 3
    count_mod = [0, 0, 0]
    for num in arr:
        count_mod[num % 3] += 1

    # Trường hợp 0: Số dư 0 + Số dư 0
    count_pairs = count_mod[0] * (count_mod[0] - 1) // 2

    # Trường hợp 1: Số dư 1 + Số dư 2
    count_pairs += count_mod[1] * count_mod[2]

    # Trường hợp 2: Số dư 1 + Số dư 1 hoặc Số dư 2 + Số dư 2
    count_pairs += count_mod[1] * (count_mod[1] - 1) // 2
    count_pairs += count_mod[2] * (count_mod[2] - 1) // 2

    return count_pairs

# Thử nghiệm
arr = [3, 5, 7, 9, 11, 13, 15]
result = count_pairs_divisible_by_3(arr)
print(f"Số lượng cặp số có tổng chia hết cho 3 là: {result}"