algoadvance

Leetcode 136. Single Number

Problem Statement:

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one. You must implement a solution with a linear runtime complexity and use only constant extra space.

Clarifying Questions:

1. Q: Can the array be empty? A: No, the array is guaranteed to be non-empty.
2. Q: Can there be negative numbers in the array? A: Yes, the array can contain both positive and negative numbers.
3. Q: Is it guaranteed that other numbers appear exactly twice except for one number? A: Yes, all other numbers will appear exactly twice.

Strategy:

To achieve a solution with linear runtime complexity ((O(n))) and constant extra space ((O(1))), you can use the XOR bitwise operation. XOR has a few useful properties:

1. (a \oplus a = 0) (any number XORed with itself is 0),
2. (a \oplus 0 = a) (any number XORed with 0 remains unchanged),
3. (a \oplus b \oplus a = b) (XOR is both associative and commutative).

With these properties, XORing all the elements in the array will cancel out all elements that appear twice, leaving the single number that appears only once.

Code:

public class SingleNumber {
    public int singleNumber(int[] nums) {
        int result = 0;
        for (int num : nums) {
            result ^= num;
        }
        return result;
    }

    // Example usage
    public static void main(String[] args) {
        SingleNumber solution = new SingleNumber();
        int[] nums = {4, 1, 2, 1, 2};
        System.out.println(solution.singleNumber(nums));  // Output will be 4
    }
}

Explanation:

• Initialization: Set result to 0.
• Iterate through the array: For each integer num in nums, XOR it with result.
• Return the result: At the end of the loop, result will hold the number that appears only once.

Time Complexity:

• Runtime Complexity: (O(n)) where (n) is the number of elements in the array. This is because we only make a single pass through the array.
• Space Complexity: (O(1)) because we are using a constant amount of extra space regardless of input size.

By using the XOR operation, we ensure that our solution is both time-efficient and space-efficient.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?