algoadvance

Leetcode 260. Single Number III

Problem Statement

Given an integer array nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once. You can return the answer in any order. Your algorithm should run in linear runtime complexity and use only constant extra space.

Clarifying Questions

1. Input Size: What is the range of the length of the input array nums?
   • You can assume 2 <= nums.length <= 3 * 10^4.
2. Range of Numbers: What is the range of the integers within the array nums?
   • The integers are within the range of -2^31 to 2^31 - 1.
3. Return Order: Does the order in which the two single numbers are returned matter?
   • No, the order does not matter.
4. Edge Cases: Are there any special cases to consider (e.g., minimal array length)?
   • Minimal length case will have 2 elements which are the two single numbers.

Strategy

To solve the problem with a time complexity of O(n) and space complexity of O(1), we can use the following strategy:

1. XOR of All Elements:
   • XOR all numbers in the array. This will result in the XOR of the two unique numbers because the numbers that appear in pairs will cancel themselves out.
2. Finding Rightmost Set Bit:
   • Find the rightmost set bit in the XOR result. This bit differentiates the two unique numbers.
3. Splitting the Numbers:
   • Divide the numbers into two groups based on the rightmost set bit identified in the previous step.
   • XOR numbers in each group to isolate the two unique numbers.

This will give us the two numbers that appear only once.

Code

public class Solution {
    public int[] singleNumber(int[] nums) {
        // Step 1: Get the XOR of the two unique numbers
        int xor = 0;
        for (int num : nums) {
            xor ^= num;
        }

        // Step 2: Get the rightmost set bit in the xor result
        int rightmostSetBit = xor & -xor;

        // Step 3: Divide numbers into two groups and XOR within each group
        int num1 = 0, num2 = 0;
        for (int num : nums) {
            if ((num & rightmostSetBit) == 0) {
                num1 ^= num;  // XOR in the first group
            } else {
                num2 ^= num;  // XOR in the second group
            }
        }

        // The result array containing the two unique numbers
        return new int[]{num1, num2};
    }
}

Time Complexity

• Time Complexity: O(n)
  • We traverse the array three times: once for calculating the XOR of all elements, once for finding the rightmost set bit, and once for dividing and calculating the final two unique numbers.
• Space Complexity: O(1)
  • We are using only a few extra variables regardless of the input size.

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?