Sansa and XOR HackerRank Solution

Sansa and XOR HackerRank Solution
Source : https://www.hackerrank.com/challenges/sansa-and-xor

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.

For example, if :

Subarray Operation Result3  None  34  None  45  None  53,4  3 XOR 4  74,5  4 XOR 5  13,4,5  3 XOR 4 XOR 5 2

Now we take the resultant values and XOR them together:

Function Description

Complete the sansaXor function in the editor below. It should return an integer that represents the results of the calculations.

sansaXor has the following parameter(s):

• arr: an array of integers

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 .
- The second line of each test case contains space-separated integers .

Constraints

Output Format

Print the results of each test case on a separate line.

Sample Input 0

231 2 344 5 7 5

Sample Output 0

20

Explanation 0

Test case 0:


Test case 1:

Sample Input 1

2398 74 12350 13 2

Sample Output 1

11048

Explanation 1

Test Case 0:

Test Case 1:

Source : https://www.hackerrank.com/challenges/sansa-and-xor

Solution

	// Karthikalapati.blogspot.com
	import java.util.Scanner;
	// XOR properties:
	// 1) x ^ x = 0
	// 2) x ^ 0 = x
	// We know that a number XORed with itself is 0. Instead of calculating the subarrays directly,
	// we calculate the number of times each number appears in any subarray. If it appears an even
	// number of times, then (x ^ x ... ^ x) where there is an even number of "x" values will give 0.
	// If there are an odd number of "x" values, the result will be "x".
	//
	// *** Case 1: n is even ***
	//
	// Each element appears an even number of times throughout the subarrays, so the answer is 0.
	//
	// *** Case 2: n is odd ***
	//
	// We notice that the odd-indexed elements appear an even number of times throughout the
	// subarrays, so xoring them together will give 0, so we can ignore the odd-indexed elements.
	//
	// The even-indexed elements in the original subarray will appear an odd number of times
	// throughout the subarrays. We can go ahead and XOR the values of the even-indexed elements
	// in the original array to get our final answer.
	// Time Complexity: O(n)
	// Space Complexity: O(1)
	static int sansaXor(int[] array) {
	if (array.length % 2 == 0) { // Case 1
	return 0;
	} else { // Case 2
	int result = 0;
	for (int i = 0; i < array.length; i++) {
	if (i % 2 == 0) {
	result ^= array[i];
	}
	}
	return result;
	}
	}
	// Discuss on HackerRank: https://www.hackerrank.com/challenges/sansa-and-xor/forum/comments/284330