Bài 4: Bài toán và thuật toán

Bạn chưa đăng nhập. Vui lòng đăng nhập để hỏi bài
Quang Bui Thanh

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.

Nguyễn Văn Tuyên
30 tháng 12 2023 lúc 11:28

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}"


Các câu hỏi tương tự
Pi Mèo
Xem chi tiết
Ngọc Thanh
Xem chi tiết
lê thị tiên
Xem chi tiết
vothu huyen
Xem chi tiết
Hoàng ST
Xem chi tiết
nguyễn bùi hương giang
Xem chi tiết
Susu
Xem chi tiết
09. Lương Trần Tuấn Dũng
Xem chi tiết
Xuân Thanh
Xem chi tiết