Count the number of subarrays with given xor K

[Question]: Problem Statement: Given an array of integers A and an integer B. Find the total number of subarrays having bitwise XOR of all elements equal to k.
Example 1:
Input Format: A = [4, 2, 2, 6, 4] , k = 6
Result: 4
Explanation: The subarrays having XOR of their elements as 6 are [4, 2], [4, 2, 2, 6, 4], [2, 2, 6], [6]

// TC: O(N)
// SC: O(N)
// Question SumWithXor
func subarraysWithXorK(_ arr: [Int], _ k: Int) ->Int {
    let arrCount = arr.count; //size of the given array.
    var xr = 0;
    var mpp:[Int: Int] = [:]
    mpp[0] = 1 //setting the value of 0.
    var cnt = 0;
    
    for i in 0..<arrCount {
        // prefix XOR till index i:
        xr = xr ^ arr[i];
        
        //By formula: x = xr^k:
        let x = xr ^ k;
        
        // add the occurrence of xr^k
        // to the count:
        cnt += mpp[x, default: 0]

        // Insert the prefix xor till index i
        // into the map:
        mpp[xr] = mpp[xr, default: 0] + 1
    }
    return cnt
}

let xorArray = [5, 6, 7, 8, 9]
let kValue = 5;
print("subarraysWithXorK ---  ", subarraysWithXorK(xorArray, kValue))// 2

Leave a Comment

Your email address will not be published. Required fields are marked *