NUHMAN.com

Introduction

LeetCode 137: Single Number II is a twist on the earlier problem where every element appears three times except for one. This problem challenges you to find that unique number in linear time and constant space using bit manipulation.

Problem Statement

Given an integer array nums where every element appears three times except for one, which appears exactly once. Find the single element and return it.

You must implement a solution with a linear runtime complexity and use only constant extra space.

Example 1:

go

Input: nums = [2,2,3,2]
Output: 3

Example 2:

go

Input: nums = [0,1,0,1,0,1,99]
Output: 99

Approach

✅ Bit Manipulation Approach (Optimal)

Here’s the key idea:

• For each bit position (0 through 31), we count how many numbers have a 1 in that bit position.
• Since every number except one appears exactly three times, the total count of bits at each position should also be a multiple of 3 if there is no unique number.
• If the total is not divisible by 3, it means the unique number has a 1 at that position.

By rebuilding the number from these unique bits, we get the result.

Steps:

1. Initialize a result variable to 0.
2. Iterate from bit 0 to 31.
3. For each bit, count how many numbers in the array have that bit set.
4. If the count is not a multiple of 3, set that bit in the result.

Go Implementation

go

package main

import (
    "fmt"
)

func singleNumber(nums []int) int {
    var result int32 = 0

    for i := 0; i < 32; i++ {
        var sum int32 = 0
        for _, num := range nums {
            sum += (int32(num) >> i) & 1
        }
        if sum%3 != 0 {
            result |= 1 << i
        }
    }

    return int(result)
}

func main() {
    nums1 := []int{2, 2, 3, 2}
    nums2 := []int{0, 1, 0, 1, 0, 1, 99}

    fmt.Println("Unique number in nums1:", singleNumber(nums1)) // Output: 3
    fmt.Println("Unique number in nums2:", singleNumber(nums2)) // Output: 99
}

Time and Space Complexity

MetricComplexityTime ComplexityO(n)Space ComplexityO(1)

• Time: We check each bit (32 total) across all n numbers, which gives us O(32 * n) = O(n).
• Space: Only a few integer variables are used, so constant space.

Edge Cases

• Negative numbers: Bitwise operations handle negative integers correctly due to two's complement representation.
• Array with only one element: The function still returns the correct unique number.

Why This Works

Imagine if we count the 1's in each bit position across all numbers. Because the repeating numbers show up three times, their bits will sum to multiples of 3. The remaining bits (those from the unique number) won't align with this rule. By isolating those bits, we rebuild the unique number.

Conclusion

LeetCode 137: Single Number II teaches a smart use of bit manipulation for identifying non-repeated numbers in a dataset with strict repetition rules. It's a perfect blend of math and logic, showing how to solve seemingly complex problems in O(n) time and O(1) space using bit-level insights. Perfect for interviews and sharpening your algorithmic thinking!