ได้รับลิสต์ nums และ queries [[x, limit], ...] สำหรับแต่ละ query หา e ∈ nums ที่ e ≤ limit และ e XOR x สูงสุด ไม่มี → -1
ตัวอย่าง
nums = [3, 5, 9], queries = [[4, 6], [2, 0]]
Output: [3, -1]
Query 1: 3^4=7, 5^4=1 → เลือก 3 | Query 2: ไม่มีเลข ≤ 0
แนวทางแก้ปัญหา
Offline Queries + Binary Trie:
- เรียง
numsและqueriesตามlimit - Insert ตัวเลขจาก
numsเข้า Trie ทีละตัว จนครบ limit ของ query นั้น - Query Trie หา max XOR: เดินทางพยายามเลือก bit ตรงข้าม (1→0, 0→1) ทุก level
การใช้งาน (Python)
class Solution:
def solve(self, A, queries):
trie = {}
def bits(x):
return map(int, bin(x)[2:].zfill(32))
def insert(x):
node = trie
for b in bits(x):
node = node.setdefault(b, {})
node[2] = x # เก็บค่าเต็มที่ leaf
def query(x):
node = trie
for b in bits(x):
want = b ^ 1
node = node.get(want, node.get(b))
return node[2]
A.sort()
# (original_index, x, limit) เรียงตาม limit
B = sorted([(i, x, lim) for i, (x, lim) in enumerate(queries)], key=lambda x: x[2])
j, n = 0, len(A)
ans = [-1] * len(queries)
for i, x, limit in B:
while j < n and A[j] <= limit:
insert(A[j])
j += 1
if j > 0: # มีตัวเลขใน trie แล้ว
ans[i] = query(x)
return ans
# ทดสอบ
ob = Solution()
print(ob.solve([3, 5, 9], [[4, 6], [2, 0]])) # Output: [3, -1]
ความซับซ้อน
- Time Complexity: O((N + Q) × 32)
- Space Complexity: O(N × 32)
