♒成雙成對 子陣列的XOR query_XOR Queries of a Subarray_Leetcode #1310

NANDKUMAR PATEL on Unsplash

題目敘述 1310. XOR Queries of a Subarray

給定一個整數陣列arr，和一串區間XOR請求queries。

請計算queries所請求的區間XOR值，並且以陣列的形式返回答案。

測試範例

Example 1:

Input: arr = [1,3,4,8], queries = [[0,1],[1,2],[0,3],[3,3]]
Output: [2,7,14,8] 
Explanation: 
The binary representation of the elements in the array are:
1 = 0001 
3 = 0011 
4 = 0100 
8 = 1000 
The XOR values for queries are:
[0,1] = 1 xor 3 = 2 
[1,2] = 3 xor 4 = 7 
[0,3] = 1 xor 3 xor 4 xor 8 = 14 
[3,3] = 8

Example 2:

Input: arr = [4,8,2,10], queries = [[2,3],[1,3],[0,0],[0,3]]
Output: [8,0,4,4]

約束條件

Constraints:

• 1 <= arr.length, queries.length <= 3 * 10^4

arr陣列 和 queries陣列長度都介於1~三萬之間。

• 1 <= arr[i] <= 10^9

每個陣列元素都介於1~十億之間。

• queries[i].length == 2

每個query標明 起點索引 和 終點索引。

• 0 <= lefti <= righti < arr.length

0 < 起點 <= 終點 < arr陣列長度

演算法 利用XOR性質 和 前綴和觀念

如果還不熟悉Prefix sum 前綴和的讀者，請參考這篇文章。

➕用Python來實現 Prefix sum 前綴和 | 小松鼠的演算法樂園 (vocus.cc)

XOR運算有一個很好的性質，同樣的變數XOR兩次會成雙成對消去=0。

A XOR A = 0

接著，再借用前綴和的觀念，建立一個prefix XOR table。

arr[0] ⊕ arr[1] ⊕ ... arr[起點-1]

⊕ arr[0] ⊕ arr[1] ⊕ ... arr[起點-1] ⊕ arr[起點] ⊕ ... ⊕ arr[終點]

= arr[起點] ⊕ ... ⊕ arr[終點]

= 題目query所求

程式碼 利用XOR性質 和 前綴和觀念

# XOR property review:
'''
Associativity:
(A XOR B) XOR C = A XOR (B XOR C)

Commutativity:
A XOR B = B XOR A

Idempotency:
A XOR A = 0
'''

class Solution:
    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
        
        result, size  = [], len(arr)
        
        look_up_table = [0] * ( size+1 )
        
        # table[i] = arr[0] XOR arr[1] XOR ... XOR arr[i-1]
        for i in range(size):
            look_up_table[i+1] = look_up_table[i] ^ arr[i]      
        
        # compute query, q, by look-up table as well as XOR property
        '''
        Left = ( prefix leading temrs )
        Right = ( prefix leading temrs ) XOR arr[ q[0] ] XOR ... XOR arr[ q[1] ]
        
        Left XOR Right = arr[ q[0] ] XOR ... XOR arr[ q[1] ]
        '''
        for q in queries:
            left = look_up_table[ q[0] ]    
            right = look_up_table[ q[1] + 1 ]
            result.append( left ^ right )
            
        return result

複雜度分析

時間複雜度: O(n + q)

O(n)時間建立prefix XOR table

O(q)計算每一條區間XOR計算請求。

空間複雜度: O(n)

需要O(n)空間來建立prefix XOR table。

Reference

[1] XOR Queries of a Subarray - LeetCode