🚀Day 05/180 (Bit Manipulation) 136. Single Number

136. Single Number

#180DaysOfDSA#DailyCodingChallenge #LeetCodeJourney #GeeksforGeeks #CodingNinjas #Codechef #CodeForces #ContinuousLearning #TechCommunity

---

Finding the Single Number in an Array

In this explanation, we'll look at a Java method that identifies the single number in an array where every other number appears exactly twice. The solution uses the XOR bitwise operation for its efficiency and simplicity.

Problem Statement

Given an array of integers, every element appears twice except for one. We need to find that single one. The solution should have a linear runtime complexity and use only constant extra space.

Approach

We will use the XOR bitwise operation to solve this problem efficiently. Here's why XOR is perfect for this:

1. Properties of XOR:

   • XOR of a number with itself is 0: a ^ a = 0

   • XOR of a number with 0 is the number itself: a ^ 0 = a

   • XOR is commutative and associative, meaning the order of operations does not matter.

Using these properties, we can XOR all the elements of the array. The pairs of duplicate elements will cancel each other out (resulting in 0), and we will be left with the single number that does not have a duplicate.

Code Explanation

Here’s the code:

class Solution {
    public int singleNumber(int[] nums) {
        int result = 0;
        for (int i = 0; i < nums.length; i++) {
            result = result ^ nums[i];
        }
        return result;
    }
}

Step-by-Step Explanation:

1. Initialization:

   • We start with a variable result initialized to 0.

2. Iterating through the Array:

   • We iterate through each element of the array using a for loop.

   • In each iteration, we apply the XOR operation between result and the current array element nums[i].

   • This step ensures that each pair of duplicate numbers cancels out (since a ^ a = 0).

3. Final Result:

   • After completing the iteration, result will hold the value of the single number that does not have a duplicate.

Example Walkthrough

Consider the array [4, 1, 2, 1, 2]:

• Initial result is 0.

• Iteration 1: result = 0 ^ 4 -> result = 4

• Iteration 2: result = 4 ^ 1 -> result = 5

• Iteration 3: result = 5 ^ 2 -> result = 7

• Iteration 4: result = 7 ^ 1 -> result = 6

• Iteration 5: result = 6 ^ 2 -> result = 4

The result after processing all elements is 4, which is the single number in the array.

Conclusion

This method is efficient because it only requires one pass through the array (O(n) time complexity) and uses a constant amount of extra space (O(1) space complexity). By leveraging the properties of the XOR operation, we can easily find the single number that appears only once in the array.