Chương trình Python tìm số cặp khớp trong mảng chứa cặp (cơ số, số)

Giả sử ta có các cặp (x, y) với x là cơ số, y là số trong cơ số đó. Trong danh sách có các cặp mang ý nghĩa giống nhau. Kiểm tra số cặp khớp (match) trong các cặp số cho trước. Các cặp có thể dư thừa, cũng có thể chứa tổ hợp cơ số-số không hợp lệ.

Ví dụ: num_inputs = 2, input_arr = [(10, 15), (8, 17)], kết quả 1. Vì 15 cơ số 10 = 17 cơ số 8.

Giải thuật

1. arr_len := len(input_arr)
2. temp_dict := defaultdict(int)
3. For i từ 0 đến num_inputs - 1:
   • num_base := str(input_arr[i][0])
   • num_val := str(input_arr[i][1])
   • temp_dict[int(num_val, int(num_base))]++
4. cnt := 0
5. Với mỗi value trong temp_dict.values():
   • cnt += value * (value - 1) // 2
6. Trả về cnt

Ví dụ

from collections import defaultdict

def solve(num_inputs, input_arr):
    arr_len = len(input_arr)
    temp_dict = defaultdict(int)
    for i in range(num_inputs):
        num_base, num_val = str(input_arr[i][0]), str(input_arr[i][1])
        temp_dict[int(num_val, int(num_base))] += 1
    cnt = 0
    for value in temp_dict.values():
        cnt += value * (value - 1) // 2
    return cnt

print(solve(2, [(10, 15), (8, 17)]))

Input

2, [(10, 15), (8, 17)]

Output

1