Đầu tiên để thuận tiện xử lý, ta chuyển các số dưới dạng hệ nhị phân thành hệ thập phân.

Xét bài toán dưới dạng đồ thị, ta có một đồ thị ~G~ gồm ~2^K~ đỉnh, ~2~ đỉnh bất kỳ sẽ có cạnh nối khi và chỉ khi chỉ số của ~2~ đỉnh đó khác nhau đúng ~1~ bit.

Ta tiến hành ~BFS~ từ tất cả các ~N~ đỉnh đã cho. Gọi ~x~ là giá trị lớn nhất của tất cả các đỉnh sau khi đã ~BFS~, rõ ràng đỉnh mang giá trị ~x~ sẽ tương ứng với việc đỉnh đó khác ~x~ bit so với ~N~ đỉnh ban đầu.

Với việc ta đã có được giá trị khác nhau ít nhất với toàn bộ ~N~ tính chất ban đầu, vậy kết quả bài toán sẽ là ~K - x~.

Độ phức tạp: ~O(N \times K + 2^K)~

Các bạn có thể tham khảo hàm ~BFS~ sau:

Code mẫu

int d[1 << 21];
queue<int> q;

int bfs() {
    int u, v, ans = 0;
    while(!q.empty()) {
        u = q.front(), q.pop();
        for(int v, i = 0; i < m; i++) {
            v = u ^ (1 << i);
            if (d[v] > d[u] + 1) {
                d[v] = d[u] + 1, ans = max(ans, d[v]);
                q.push(v);
            }
        }
    }
    return ans;
}