Với mảng n-1 * n, tìm số bị thiếu

Question

Ở đây mỗi hàng có chứa một biểu diễn bit của một số. Các số này đến từ 1..NChúng chính xác một số bị thiếu.Tìm thấy biểu diễn bit của số bị thiếu.
Người phỏng vấn đã hỏi tôi câu hỏi này.
Tôi đã nói: "Chúng tôi có thể tìm tổng của các số đã cho và trừ nó khỏi tổng số n đầu tiên (chúng tôi biết là (N * (N + 1))/2)"
từ cơ sở 10 đến cơ sở 2.
Bạn có thể cho tôi một gợi ý về cách tôi có thể giải quyết nó mà không thay đổi cơ sở?

Answer 1

Bạn có thể XOR cùng nhau tất cả các số từ 0 .. N phạm vi, sau đó XOR các số từ mảng. Kết quả sẽ là số bị thiếu.

Giải thích:XOR nhập số bằng chính nó luôn dẫn đến 0. Thuật toán trên XOR s mỗi số chính xác hai lần, ngoại trừ số bị thiếu. Số bị thiếu sẽ là XOR -ed với số không chính xác một lần, do đó kết quả sẽ bằng số bị thiếu.

Lưu ý: người phỏng vấn là sai trên cần phải chuyển đổi các căn cứ để làm bổ sung: thêm số nhị phân rất dễ dàng và vui vẻ - trong thực tế, máy tính làm điều đó tất cả các thời gian :-)

Answer 2

Bạn chỉ có thể XOR những các số cùng nhau và XOR với 1..n. Thực tế là các số được lưu trữ trong nhị phân là một gợi ý tốt, BTW. Trên thực tế, bất kỳ toán tử giao hoán nào có nghịch đảo đều hoạt động, vì nếu toán tử giao hoán, thứ tự không quan trọng, vì vậy nó có thể được áp dụng cho các số bạn có và 1..n, với sự khác biệt là đầu tiên không hoạt động trên số không nằm trong mảng. Sau đó, bạn có thể sử dụng nghịch đảo của nó để tìm số đó, với hai kết quả bạn có. SO + và -, * và /, XOR và XOR và bất kỳ nhà khai thác nào khác đáp ứng yêu cầu đều phải hoạt động tại đây.