Single Number

Given an array where every element appears twice except for one, you need to find that single element with linear runtime complexity and constant extra space.

One way to achieve this is by using the XOR operator. When you XOR a number with itself, the result is 0. When you XOR a number with 0, the result is the number itself. So, if you XOR all the numbers in the array, the numbers that appear twice will cancel each other out, and you’ll be left with the number that appears only once.

Here’s the code:

1
2
3
4
5
6

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        result = 0
        for num in nums:
            result ^= num
        return result

Explanation

  • Initialize the result as 0.
  • Iterate through all the numbers in the array.
  • Use the XOR (^) operator on each number with the result.
  • Since every number appears twice except one, the XOR operation will cancel out all the numbers that appear twice, leaving only the number that appears once.

Key Takeaway

By leveraging the properties of the XOR operator, this solution efficiently finds the single number that doesn’t appear twice in the array. It meets the specified constraints of linear runtime complexity and constant extra space.

Identifying Problem Isomorphism

“Single Number” involves finding the number that appears only once in an array where all other elements appear twice. This problem utilizes the XOR bitwise operation, capitalizing on the property that any number XORed with itself equals zero and any number XORed with zero equals the original number.

A related problem is “137. Single Number II”. In this problem, you’re asked to find the number that appears only once in an array while all others appear three times. Despite the apparent difference in problem conditions, the underlying methodology to solve both problems is still the same - leveraging bitwise operations to identify the single occurring element.

In both problems, the fundamental principle is understanding and applying bitwise operations to process arrays for special conditions. Therefore, this forms an approximate mapping.

Understanding and solving these problems enhance your familiarity with bitwise operations and their varied applications in array processing tasks.

title: Single Number excerpt: This covers using XOR operation to find unique number in an array. tags: logical-xor-operator

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

Follow up: Could you implement a solution with a linear runtime complexity and without using extra memory?

Example 1:

Input: nums = [2,2,1]
Output: 1
Example 2:

Input: nums = [4,1,2,1,2]
Output: 4
Example 3:

Input: nums = [1]
Output: 1

Constraints

  • 1 <= nums.length <= 3 * 10^4
  • -3 * 10^4 <= nums[i] <= 3 * 10^4

Each element in the array appears twice except for one element which appears only once.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

# @param {Integer[]} nums
# @return {Integer}
def single_number(nums)
  result = 0
  
  for n in nums
    result = n ^ result
  end
  
  return result
end
  • Key concept here is how XOR operator works. When applied to the same integers it returns 0.
  • Therefore we can use it to XOR all the numbers, each duplicate pair will cancel out and the remaining element will be the unique one.

Building Block

  • Logical XOR Operator

Identifying Problem Isomorphism

“Single Number” is simpler than “Single Number II”.

In “Single Number”, you can use the property of the XOR operation to find the number that appears only once in the array. Since the XOR operation on two same numbers gives 0 and any number XORed with 0 gives the original number, one pass over the array with XOR operation will give the single number. This is a straightforward application of the XOR operation.

“Single Number II” requires a more complex approach. In this problem, each element appears three times except for one, which appears exactly once. While bitwise operations are still used, the solution isn’t as straightforward as using a single XOR operation. The approach typically involves using additional bitwise operations (AND, NOT) and sometimes additional space, which makes the problem more complex.

1
2
3
4
5
6

class Solution(object):
    def singleNumber(self, nums):
        uniqNum = 0
        for idx in nums:
            uniqNum ^= idx
        return uniqNum

Problem Classification

  1. Array Manipulation: The problem involves manipulating an array of integers. Specifically, it requires processing the array to find a particular value.

  2. Bit Manipulation: The problem specifically uses the XOR bitwise operator to solve the problem. This is a common category for problems that involve bitwise operations.

  3. Searching: Although not explicitly stated, the problem requires finding a specific element in the array. This is a key characteristic of search problems.

  4. Single-element Identification: This is a more specific classification. The problem involves identifying an element that meets a particular condition (in this case, the element that appears only once in the array).

Language Agnostic Coding Drills

This solution makes use of bitwise operations and iterates through the list/array of numbers. Here’s how we can separate the key concepts into drills:

  1. Drill 1 - Iteration over a Collection: In many languages, you’ll need to know how to iterate over a collection of items (like a list or array). This drill would involve writing a loop that visits each item in a collection one by one.

  2. Drill 2 - Bitwise XOR operation: XOR operation is a bitwise operation that takes two bits and returns 1 if exactly one of the bits is 1, otherwise it returns 0. This drill will involve performing the XOR operation on two numbers.

  3. Drill 3 - Updating a variable’s value: During each iteration, the code updates the value of uniqNum by applying the XOR operation with the current number. This drill would involve learning how to update the value of a variable based on some operation with its current value.

  4. Drill 4 - Using a variable to hold a result: In this problem, uniqNum is initialized to 0 and then updated through each iteration. The final value of uniqNum is then returned as the result. This drill would involve using a variable to keep track of a result over time.

Now let’s break down the problem-solving approach:

  1. Initialize a variable: Start by initializing a variable to 0. This variable will be used to hold the unique number in the array. In the code, this variable is uniqNum.

  2. Iterate through the array: Next, go through each number in the array.

  3. Apply the XOR operation: For each number in the array, apply the XOR operation to it and uniqNum, then update uniqNum with this new value.

  4. Return the result: After going through all the numbers, the value of uniqNum will be the unique number that appears only once in the array. This is the result to return.

In a XOR operation, a number XOR’d with itself results in 0, and any number XOR’d with 0 results in the original number. Therefore, the single number that appears once in the array will survive the XOR operations, while the other numbers that appear twice will XOR to 0, leaving uniqNum with the value of the single number.

Targeted Drills in Python

Drill 1 - Iteration over a Collection: Here, we will iterate over a list of integers.

1
2
3
4

nums = [4, 1, 2, 1, 2]

for i in nums:
    print(i)

Drill 2 - Bitwise XOR operation: Here, we will take two integers and perform a XOR operation on them.

1
2
3
4
5

a = 5  # binary: 101
b = 3  # binary: 011

result = a ^ b
print(result)  # prints: 6 (binary: 110)

Drill 3 - Updating a variable’s value: Here, we will update a variable’s value in each iteration.

1
2
3
4
5
6

nums = [4, 1, 2, 1, 2]
uniqNum = 0

for i in nums:
    uniqNum += i  # we're adding here for simplicity. The actual problem uses XOR (^)
    print(uniqNum)

Drill 4 - Using a variable to hold a result: Here, we are using a variable uniqNum to hold the result of XOR operations. After the loop, we print the result.

1
2
3
4
5
6
7

nums = [4, 1, 2, 1, 2]
uniqNum = 0

for i in nums:
    uniqNum ^= i  # ^= is shorthand for uniqNum = uniqNum ^ i

print(uniqNum)  # prints: 4

Integrated Drill:

Finally, integrating all these drills gives us the solution for our problem.

1
2
3
4
5
6

class Solution(object):
    def singleNumber(self, nums):
        uniqNum = 0
        for idx in nums:
            uniqNum ^= idx
        return uniqNum

This is the complete problem-specific drill in Python. Here, we used all the concepts that we have learned in previous drills. Each number is XORed with the uniqNum. In the end, uniqNum contains the number that appears only once.