LeetCode 137: Single Number II Solution

Problem Explanation

Explanation

To solve this problem with linear runtime complexity and constant extra space, we can utilize bitwise operations, specifically bitwise manipulation. The key idea is to count the occurrences of each bit position in all the numbers and then use bitwise operations to determine the single number that appears once.

We can iterate through all the numbers and keep track of the total count of each bit position mod 3. This way, for each bit position, we will have either 0 or 1 as the count, representing the single number.

Algorithmic Steps:

Initialize three variables ones, twos, and common. Initially, set ones to 0, twos to 0, and common to 0.
Iterate through each number in the array:
- Update twos to include the common bits between twos and the current number.
- Update ones to include the common bits between ones and the current number, but not in twos.
- Update common by bitwise ANDing ones and twos to reset the common bits in ones and twos.
Return ones as the single number that appears once.

Time Complexity:

The time complexity of this solution is O(n) where n is the number of elements in the input array.

Space Complexity:

The space complexity of this solution is O(1) since we are using only a constant amount of extra space.

Solution Code

class Solution {
    public int singleNumber(int[] nums) {
        int ones = 0, twos = 0, common = 0;
        for (int num : nums) {
            twos |= ones & num;
            ones ^= num;
            common = ones & twos;
            ones &= ~common;
            twos &= ~common;
        }
        return ones;
    }
}

Frequently Asked Questions

How to solve LeetCode 137 (Single Number II)?

This page provides optimized solutions for LeetCode problem 137 (Single Number II) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 137 (Single Number II)?

The time complexity for LeetCode 137 (Single Number II) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 137 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 137 in Java, C++, or Python.