Bit Manipulation: Lonely Integer HackerRank Solution

Bit Manipulation: Lonely Integer HackerRank Solution
Source : https://www.hackerrank.com/challenges/ctci-lonely-integer

Consider an array of integers where all but one of the integers occur in pairs. In other words, every element occurs exactly twice except for one unique element. Find the unique element.

For example, given the array , you would return .

Function Description

Complete the findLonely function in the editor below. It should return the unique integer in .

findLonely has the following parameter(s):

• arr: an array of integers

Input Format

The first line contains a single integer, , denoting the number of integers in .
The second line contains space-separated integers, each an element, .

Constraints

• It is guaranteed that is an odd number.
• , where .

Output Format

Print the unique number in on a new line.

Sample Input 0

11

Sample Output 0

1

Explanation 0
The array only contains a single , so we print as our answer.

Sample Input 1

31 1 2

Sample Output 1

2

Explanation 1
We have two 's and one . We print , because that's the only unique element in the array.

Sample Input 2

50 0 1 2 1

Sample Output 2

2

Explanation 2
We have two 's, two 's, and one . We print , because that's the only unique element in the array.

Source : https://www.hackerrank.com/challenges/ctci-lonely-integer

Solution

	// Karthikalapati.blogspot.com
	// O(n) runtime. O(1) space. Uses XOR. Keep in mind:
	// 1) x ^ x = 0
	// 2) x ^ 0 = x
	// 3) XOR is commutative and associative
	int findLonely(List<Integer> array) {
	int val = 0;
	for (int num : array) {
	val = val ^ num; // ^ is XOR operator
	}
	return val;
	}