Find the Unique Number in Duplicates Array: Meta SDE Interview Question

One common topic frequently appearing in Meta's SDE interviews is the manipulation and analysis of arrays.

In this article, we will explore a specific array problem asked in Meta's interviews for SDE roles.

Problem Statement:

Imagine an array of numbers where every number occurs twice. However, one number appears only once. How would you find this number in O (log n) time?

Solution:

To solve this problem, we can use the concept of binary search along with the property of XOR operation.

Concept:

• XOR of a number with itself is 0.
• XOR of a number with 0 is the number itself.
• XOR is commutative and associative.

Approach:

1. Use binary search to divide the array into two halves.
2. Since every number except one occurs twice, the single number will disrupt the pairing.
3. Compare the end elements of the halves to decide which half to search next.
4. Continue the binary search until you find the single number.

Things to consider:

• The array must be sorted for binary search.
• If the array is not sorted, sort it first, which will take O(n log n) time, violating the O(log n) requirement.

The problem statement suggests that the array is already sorted since we're aiming for a solution with O(log n) time complexity.

Here's a Python code snippet using binary search to find the single number:

def findSingleNumber(nums):
    low, high = 0, len(nums) - 1

    while low < high:
        mid = low + (high - low) // 2
        # Check if the mid is at the correct pair index
        if mid % 2 == 0:
            if nums[mid] == nums[mid + 1]:
                low = mid + 2
            else:
                high = mid
        else:
            if nums[mid] == nums[mid - 1]:
                low = mid + 1
            else:
                high = mid - 1

    return nums[low]

# Example usage:
print(findSingleNumber([1, 1, 2, 3, 3, 4, 4, 8, 8]))  # Output: 2

Time Complexity: O(log n) - due to the binary search.

Space Complexity: O(1) - no additional space is used.

This code assumes that the array is sorted and every number except one appears exactly twice.

The single number can be found using the binary search technique by checking the pairing of the numbers.

If the pairing is off, it means the single number is on the left; otherwise, it's on the right.

****

This problem tests your understanding of arrays and challenges you to think creatively and devise efficient solutions under specific constraints.

If you would like to practice more such coding challenges, feel free to reach out to me.

As an experienced Software Development Engineer at Meta and a mentor, I'd be happy to guide you through similar problems and help you strengthen your problem-solving skills.

Happy Coding!

Also read: 👇

Mastering the Binary Tree LCA Problem for Amazon SDE Interviews