HackerRank Lonely Integer Java Solution Explained
Problem Overview
Original Problem: Lonely Integer| HackerRank
Difficulty: Easy
Category: Arrays, Bit Manipulation
Description: Given an array of integers where every element appears exactly twice except for one element that appears once, find and return the unique (lonely) element.
This problem, part of HackerRank’s One Week Preparation Kit, is an excellent exercise for beginners to explore array processing and bit manipulation in Java, key skills for coding interviews.
Understanding the Problem
The Lonely Integer problem asks you to find the single integer in an array that appears only once, while all other integers appear exactly twice. For example, in the array [7, 3, 5, 3, 5], the numbers 3 and 5 each appear twice, but 7 appears once, so 7 is the lonely integer. The array always has an odd number of elements, and the constraints guarantee exactly one unique element. The goal is to return this element efficiently.
Input and Output
Input:
First line: An integer n, the size of the array.
Second line: n space-separated integers a[i].
Output:
An integer representing the element that appears only once in the array.
Constraints:
1 ≤ n < 100
n is odd.
0 ≤ a[i] ≤ 100
Exactly one element appears once; all others appear twice.
Initial Reasoning
To solve this, we need to identify the element that appears only once in an array where all other elements are paired. Possible approaches include:
Using a HashMap: Count occurrences of each number and find the one with a count of 1.
Using Bit Manipulation: Use XOR, as XORing a number with itself yields 0, and XORing with 0 yields the number itself.
Sorting: Sort the array and check for the unpaired element.
The XOR approach is optimal because it requires O(n) time and O(1) space, leveraging the problem’s guarantee that all elements except one appear twice. This is also beginner-friendly once the XOR concept is explained.
Thought Process
Let’s break down the solution using the XOR approach:
Understand XOR Properties:
a XOR a = 0 (a number XORed with itself cancels out).
a XOR 0 = a (a number XORed with 0 remains unchanged).
XOR is associative and commutative, so order doesn’t matter.
If we XOR all elements in the array, paired elements (appearing twice) cancel out to 0, leaving only the lonely integer.
Process the Array:
Iterate through the array once, XORing each element with a running result.
After the loop, the result is the lonely integer.
Handle Constraints:
The array size is small (n < 100), so any approach is fast enough, but XOR is most efficient in terms of space.
Elements are non-negative and small (0 ≤ a[i] ≤ 100), so int is sufficient.
The guarantee of an odd n and exactly one unique element ensures the XOR result is valid.
Edge Cases:
If n = 1, the array has one element, which is the lonely integer (XOR with 0 returns the element).
For larger arrays, the XOR approach works regardless of element order or duplicates.
Pseudocode
// lonelyInteger method:
Initialise result variable to 0
For each element in the array
XOR the element with the current result value
Return the result
Solution Code
// Note: This is one of many possible solutions
// Note: Variable and method names have been updated from the original template for clarity and to follow Java naming conventions (e.g., 'a' to 'numbers')
import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;
class Result {
public static int lonelyInteger(List<Integer> numbers) {
// Initialize result for XOR operation
int result = 0;
// XOR all elements; paired elements cancel out, leaving the lonely integer
for (int element : numbers) {
result ^= element;
}
return result;
}
}
public class Solution {
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
int arrayLength = Integer.parseInt(bufferedReader.readLine().trim());
List numbers = Stream.of(bufferedReader.readLine().replaceAll("\\s+$", "").split(" "))
.map(Integer::parseInt)
.collect(toList());
int result = Result.lonelyInteger(numbers);
bufferedWriter.write(String.valueOf(result));
bufferedWriter.newLine();
bufferedReader.close();
bufferedWriter.close();
}
} Step-by-Step Explanation
Let’s break down the Java solution for beginners:
Input Handling:
The main method reads:
The array size, using Integer.parseInt(bufferedReader.readLine().trim()).
A line of n space-separated integers, processed into a List<Integer> using Stream.of and map(Integer::parseInt).
Initialize XOR Result:
In lonelyInteger, initialize result to 0. This will store the running XOR of all elements.
Starting with 0 ensures the first XOR operation (0 XOR element) yields element.
XOR Operation:
Iterate through the array using a for-each loop.
For each element, update result = result ^ element, where ^ is the bitwise XOR operator.
Paired elements cancel out (e.g., 3 ^ 3 = 0), so after the loop, result holds the lonely integer.
Return the Result:
Return result, which is the integer that appears only once.
The constraints (0 ≤ a[i] ≤ 100) ensure the result fits in an int.
Output Handling:
In the main method, write the result to the output file using bufferedWriter.write(String.valueOf(result)).
Add a newline with bufferedWriter.newLine().
Close bufferedReader and bufferedWriter to prevent resource leaks.
Common Mistakes to Avoid
Here are common pitfalls for beginners:
Using a HashMap Unnecessarily: While a HashMap to count occurrences works, it uses O(n) extra space, whereas XOR uses O(1) space, which is more efficient.
Misunderstanding XOR: Beginners might not realize that XORing a number with itself yields 0. Practice with small examples (e.g., [1, 2, 1] → 1 ^ 2 ^ 1 = 2) to understand this.
Ignoring Constraints: Assuming the array might not have a lonely integer or that n could be even can lead to overcomplicated code. The constraints guarantee one unique element and an odd n.
Real-World Application
The Lonely Integer problem’s XOR approach is useful in scenarios like error detection and data processing. For example, in networking, XOR can identify a single corrupted bit in a stream of paired data. In database systems, it can help find a unique record in a dataset with paired entries. This problem introduces bit manipulation, a technique used in low-level programming, cryptography, and optimization tasks.
FAQs
Q: Why does XOR work for this problem?
A: XORing a number with itself yields 0, and XORing with 0 yields the number. Since all elements except one appear twice, paired elements cancel out, leaving the lonely integer.
Q: Can I use a HashMap instead of XOR?
A: Yes, you can count occurrences in a HashMap and find the element with a count of 1, but it uses O(n) space compared to XOR’s O(1) space.
Q: What if the array has only one element?
A: If n = 1, the single element is the lonely integer. The XOR approach still works, as 0 XOR element= element.