Hackerrank: Sansa and XOR

Bit Manipulation

Problem Statement

Sansa has an array. She wants to find the value obtained by XOR-ing the contiguous subarrays, followed by XOR-ing the values thus obtained. Determine this value.

Function Description

Complete the sansaXor function in the editor below.

sansaXor has the following parameter(s):

• int arr[n]: an array of integers

Returns

• int: the result of calculations

Input Format

The first line contains an integer, the number of the test cases.

Each of the next pairs of lines is as follows:
- The first line of each test case contains an integer, the number of elements in arr.
- The second line of each test case contains space-separated integers arr[i].

Constraints:

1 ≤ t ≤ 5

2 ≤ n ≤ 10⁵

1 ≤ arr[i] ≤ 10⁸

Brute Force Approach:

Step 1: We initialize an answer variable to zero( a ^ 0 = 0 ).

Step 2: We iterate through the array using two for loops to get the subarrays.

Step 3: Find XOR of the elements of the subarray and XOR it with the final answer

Step 4: return the answer

def xor(arr):
    if len(arr)==1:
        return arr[0]
    ans = 0
    for i in arr:
        ans = ans^i
    return ans
def sansaXor(arr):
    n = len(arr)
    ans = 0
    for i in range(n):
        for j in range(i+1,n+1):
            ans = ans^xor(arr[i:j])
    return ans

Time Complexity: O(n³)

Space Complexity: O(1)

As the time complexity is n³ it is going to give TLE(Time Limit Exceeded Error) for larger inputs.

Optimized Approach:

From the properties of XOR operations, We know that

a ^ a = 0

a ^ 0 = 0

Let us understand with an example, [1, 2, 3, 4]

The possible sub-arrays are:

1
1 2
1 2 3
1 2 3 4
2
2 3
2 3 4
3 4
4

We can see that the numbers are repeating and get cancelled out in the final answer. We have to find the number of times a number is repeated in the entire subarrays.

By observation and some logic, the number of times it repeats is

( len(arr) — index ) * ( index+1 )

If this value is a multiple of 2, all the numbers will get cancelled. Otherwise, we XOR it with the final answer.

def sansaXor(arr):
    n = len(arr)
    ans = 0
    for i in range(n):
        times = (n-i)*(i+1)
        if times&1==1:
            ans = ans^arr[i]
    return ans

Thanks For Reading. Happy Coding.