Find the Unique Element in an Array Efficiently: Masai DSA

Problem Statement

In this problem, you are given a number N, and an array that contains numbers from 1 to N, but with a unique twist: every number appears twice, except for one, which appears only once. Your task is to find that single number.

This type of problem is commonly asked in DSA (Data Structures and Algorithms) interviews, and understanding how to efficiently solve it is essential for competitive programming.

Approach to Solve the Problem

1. Sorting and Pair Checking

A simple way to find the unique element is:

• Sort the array (so that duplicate elements come together).
• Iterate through the sorted array and check adjacent elements.
• The element that does not have a duplicate is our answer.

This approach has a time complexity of O(N log N) (because of sorting), and a space complexity of O(1).

Code Implementation (JavaScript)

function runProgram(input) {
var input = input.split("\n");
var t = +input[0]; // Number of test cases
var line = 1;
for (var i = 0; i < t; i++) {
var N = +input[line]; // Size of the array
line++;
var arr = input[line].trim().split(" ").map(Number);
line++;
solve(N, arr);
}
}

function solve(N, arr) {
arr.sort((a, b) => a - b); // Sort the array

var i = 0;
while (i < 2 * N - 1) {
if (arr[i] !== arr[i + 1]) { // If the current element is not equal to the next one
console.log(arr[i]); // Print the unique element
break;
}
i += 2; // Move to the next pair
}
}

// Handling input for different environments
if (process.env.USER === "") {
runProgram(``);
} else {
process.stdin.resume();
process.stdin.setEncoding("ascii");
let read = "";
process.stdin.on("data", function (input) {
read += input;
});
process.stdin.on("end", function () {
read = read.replace(/\n$/, "");
read = read.replace(/\n$/, "");
runProgram(read);
});
process.on("SIGINT", function () {
read = read.replace(/\n$/, "");
runProgram(read);
process.exit(0);
});
}

Explanation of the Code

1. Reading Input:

   • The program first reads the input and splits it into lines.
   • The first line contains T (number of test cases).
   • For each test case, it reads N and the corresponding array.

2. Sorting the Array:

   • Sorting ensures that duplicate numbers come together.

3. Finding the Unique Element:

   • The loop iterates through the sorted array in steps of 2.
   • If an element does not have a duplicate (i.e., it doesn’t match the next element), we print it as the answer.
   • The loop breaks as soon as we find the unique element.
     

     Optimized Approach (Using XOR – O(N) Time, O(1) Space)

     Instead of sorting, we can use bitwise XOR to solve the problem in O(N) time with O(1) space.

     How XOR Works?

     • XOR (^) of two same numbers is 0 → a ^ a = 0
     • XOR of a number with 0 is the number itself → a ^ 0 = a
     • XOR is commutative and associative → a ^ b ^ a = (a ^ a) ^ b = 0 ^ b = b

     Optimized Code (Using XOR)

     function solve(N, arr) {
     let unique = 0;
     for (let num of arr) {
     unique ^= num; // XOR all elements
     }
     console.log(unique);
     }

   • Complexity Analysis

     Approach	Time Complexity	Space Complexity
     Sorting + Pair Checking	O(N log N)	O(1)
     XOR (Optimized)	O(N)	O(1)

     Conclusion

     This problem is a great example of Masai DSA concepts, testing knowledge of: ✅ Sorting Algorithms
     ✅ Bitwise Operations (XOR)
     ✅ Efficient Array Manipulation

     The sorting method is easier to understand but less efficient, while the XOR method is more optimized for larger inputs. Keep practicing such problems to enhance your DSA skills for competitive programming! 💡🔥

     🔗 For more such DSA problems, stay tuned to Masai DSA tutorials! 🚀