Tìm phần tử mất từ mảng trùng lặp trong Python

Cho hai mảng trùng lặp nhau trừ một phần tử (một mảng thiếu một phần tử so với mảng kia). Tìm phần tử thiếu đó.

Ví dụ: A = [2, 5, 6, 8, 10], B = [5, 6, 8, 10] → Kết quả: 2.

Thuật toán Binary Search

1. Hàm solve(A, B, N) giả định A dài hơn B 1 phần tử.
2. Nếu N=1 hoặc A[0]≠B[0] → trả về A[0].
3. Binary search: low=0, high=N-1. So sánh A[mid] và B[mid]. Nếu bằng nhau → phần tử thiếu ở bên phải (low=mid), ngược lại bên trái (high=mid).
4. Khi low == high - 1 dừng, trả về A[high].
5. Hàm chính so sánh độ dài hai mảng để quyết định gọi solve theo hướng nào.

Ví dụ code

def solve(A, B, N):
    if N == 1:
        return A[0]
    if A[0] != B[0]:
        return A[0]
    low, high = 0, N - 1
    while low < high:
        mid = (low + high) // 2
        if A[mid] == B[mid]:
            low = mid
        else:
            high = mid
        if low == high - 1:
            break
    return A[high]

def get_missing_element(A, B):
    M, N = len(A), len(B)
    if N == M - 1:
        return solve(A, B, M)
    elif M == N - 1:
        return solve(B, A, N)
    else:
        return "Not found"

A = [2, 5, 6, 8, 10]
B = [5, 6, 8, 10]
print(get_missing_element(A, B))

Input

[2, 5, 6, 8, 10], [5, 6, 8, 10]

Output

2