Single Number II (Three Copies)

🎯

Single Number II (Three Copies)

mediumBIT_MANIPULATIONAmazonFacebookGoogle

Imagine you have a large dataset where every number appears exactly three times except one unique number that appears only once. Finding that unique number efficiently can help in error detection or data integrity checks.

💡 This problem is a classic bit manipulation challenge where the goal is to find a unique element among triplicates. Beginners often struggle because the straightforward XOR trick for pairs doesn't directly apply here, requiring a deeper understanding of bit counting and modular arithmetic.

📋

Problem Statement

Given an integer array nums where every element appears exactly 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.

1 ≤ nums.length ≤ 10^5-2^31 ≤ nums[i] ≤ 2^31 - 1Every element appears exactly three times except for one element which appears once.

💡

Example

Input"[2, 2, 3, 2]"

Output3

2 appears three times, 3 appears once, so 3 is the unique number.

Input"[0,1,0,1,0,1,99]"

Output99

0 and 1 appear three times each, 99 appears once.

• Array with only one element → returns that element
• All elements are negative except the unique one → returns unique correctly
• Unique element is zero → returns zero
• Large array with maximum allowed size → solution must be efficient

⚠️

Common Mistakes

Using XOR directly as in Single Number I

Fails because XOR cancels pairs, but here elements appear thrice

✅ Use bit counting modulo 3 or FSM approach instead

Not handling negative numbers correctly in bit counting

Incorrect result due to sign bit misinterpretation

✅ Handle 31st bit as sign bit and adjust result accordingly

Using extra space in bit counting approach (e.g., arrays of size n)

Excessive memory usage, not meeting constant space requirement

✅ Use fixed 32-bit counters only

Incorrectly updating ones and twos in FSM approach

Bits not cleared properly, leading to wrong final result

✅ Use common mask to clear bits appearing three times from both ones and twos

🧠

Brute Force (Hash Map Counting)

💡 This approach uses a hash map to count occurrences of each number. It's straightforward and helps beginners understand the problem but is not optimal in space.

Intuition

Count how many times each number appears, then find the one that appears once.

Algorithm

1. Initialize an empty hash map to store counts.
2. Iterate through the array, incrementing the count for each number.
3. Iterate through the hash map to find the number with count 1.
4. Return that number.

💡 This approach is easy to understand but uses extra space proportional to input size, which is not ideal for large datasets.

</>

Code

from collections import Counter

def singleNumber(nums):
    counts = Counter()
    for num in nums:
        counts[num] += 1
    for num, count in counts.items():
        if count == 1:
            return num

# Driver code
if __name__ == '__main__':
    print(singleNumber([2,2,3,2]))  # Output: 3

Line Notes

from collections import CounterImports Counter for easy frequency counting

counts = Counter()Initialize counter to store frequencies

for num in nums:Iterate over each number to count occurrences

if count == 1:Identify the unique number appearing once

import java.util.HashMap;
import java.util.Map;

public class Solution {
    public static int singleNumber(int[] nums) {
        Map<Integer, Integer> counts = new HashMap<>();
        for (int num : nums) {
            counts.put(num, counts.getOrDefault(num, 0) + 1);
        }
        for (Map.Entry<Integer, Integer> entry : counts.entrySet()) {
            if (entry.getValue() == 1) {
                return entry.getKey();
            }
        }
        return -1; // Should never reach here
    }

    public static void main(String[] args) {
        System.out.println(singleNumber(new int[]{2,2,3,2})); // Output: 3
    }
}

Line Notes

Map<Integer, Integer> counts = new HashMap<>()Create map to store counts

for (int num : nums)Loop through array to count each number

counts.put(num, counts.getOrDefault(num, 0) + 1)Increment count for current number

if (entry.getValue() == 1)Find the number that appears once

#include <iostream>
#include <unordered_map>
#include <vector>

using namespace std;

int singleNumber(vector<int>& nums) {
    unordered_map<int, int> counts;
    for (int num : nums) {
        counts[num]++;
    }
    for (auto& p : counts) {
        if (p.second == 1) return p.first;
    }
    return -1; // Should never reach here
}

int main() {
    vector<int> nums = {2,2,3,2};
    cout << singleNumber(nums) << endl; // Output: 3
    return 0;
}

Line Notes

#include <unordered_map>Include hash map for frequency counting

unordered_map<int, int> counts;Map to store counts of each number

for (int num : nums)Iterate over input array

if (p.second == 1) return p.first;Return the unique number

function singleNumber(nums) {
    const counts = new Map();
    for (const num of nums) {
        counts.set(num, (counts.get(num) || 0) + 1);
    }
    for (const [num, count] of counts.entries()) {
        if (count === 1) return num;
    }
    return -1; // Should never reach here
}

// Test
console.log(singleNumber([2,2,3,2])); // Output: 3

Line Notes

const counts = new Map()Initialize map to count frequencies

for (const num of nums)Iterate over each number in array

counts.set(num, (counts.get(num) || 0) + 1)Increment count for current number

if (count === 1) return numReturn the unique number found

⏱

Complexity

TimeO(n)

SpaceO(n)

We iterate through the array once to count frequencies and once over the map to find the unique number. The map can grow up to size n in worst case.

💡 For n=100,000, this means about 200,000 operations and memory proportional to n, which can be large.

Interview Verdict: Accepted but not optimal

This approach works but uses extra memory, which is not ideal for large inputs or strict space constraints.

🧠

Bit Counting with Modulo 3

💡 This approach uses bit manipulation to count how many times each bit is set across all numbers, then uses modulo 3 to isolate the unique number's bits.

Intuition

If every number except one appears three times, then the sum of bits at each position is a multiple of 3 except for the unique number's bits.

Algorithm

1. Initialize an integer result to 0.
2. For each bit position from 0 to 31:
3. Count how many numbers have that bit set.
4. Take the count modulo 3; if remainder is 1, set that bit in the result.
5. Return the result.

💡 This algorithm cleverly uses the property of modulo to filter out bits contributed by triplicates, leaving only the unique number's bits.

</>

Code

def singleNumber(nums):
    result = 0
    for i in range(32):
        bit_sum = 0
        for num in nums:
            bit_sum += (num >> i) & 1
        if bit_sum % 3 != 0:
            # Handle negative numbers for 31st bit
            if i == 31:
                result -= (1 << i)
            else:
                result |= (1 << i)
    return result

# Driver code
if __name__ == '__main__':
    print(singleNumber([2,2,3,2]))  # Output: 3

Line Notes

result = 0Initialize result to accumulate bits of unique number

for i in range(32)Iterate over all 32 bit positions

bit_sum += (num >> i) & 1Count how many numbers have current bit set

if bit_sum % 3 != 0If remainder is 1, unique number has this bit set

public class Solution {
    public static int singleNumber(int[] nums) {
        int result = 0;
        for (int i = 0; i < 32; i++) {
            int bitSum = 0;
            for (int num : nums) {
                bitSum += (num >> i) & 1;
            }
            if (bitSum % 3 != 0) {
                if (i == 31) {
                    result -= (1 << i);
                } else {
                    result |= (1 << i);
                }
            }
        }
        return result;
    }

    public static void main(String[] args) {
        System.out.println(singleNumber(new int[]{2,2,3,2})); // Output: 3
    }
}

Line Notes

int result = 0Initialize result to store unique number bits

for (int i = 0; i < 32; i++)Check each bit position

bitSum += (num >> i) & 1Count set bits at position i

if (bitSum % 3 != 0)If remainder is 1, set bit in result

#include <iostream>
#include <vector>

using namespace std;

int singleNumber(vector<int>& nums) {
    int result = 0;
    for (int i = 0; i < 32; i++) {
        int bitSum = 0;
        for (int num : nums) {
            bitSum += (num >> i) & 1;
        }
        if (bitSum % 3 != 0) {
            if (i == 31) {
                result -= (1 << i);
            } else {
                result |= (1 << i);
            }
        }
    }
    return result;
}

int main() {
    vector<int> nums = {2,2,3,2};
    cout << singleNumber(nums) << endl; // Output: 3
    return 0;
}

Line Notes

int result = 0Initialize result to accumulate bits

for (int i = 0; i < 32; i++)Iterate over all bit positions

bitSum += (num >> i) & 1Count how many numbers have bit i set

if (bitSum % 3 != 0)Set bit in result if remainder is 1

function singleNumber(nums) {
    let result = 0;
    for (let i = 0; i < 32; i++) {
        let bitSum = 0;
        for (const num of nums) {
            bitSum += (num >> i) & 1;
        }
        if (bitSum % 3 !== 0) {
            if (i === 31) {
                result -= (1 << i);
            } else {
                result |= (1 << i);
            }
        }
    }
    return result;
}

// Test
console.log(singleNumber([2,2,3,2])); // Output: 3

Line Notes

let result = 0Initialize result to store unique bits

for (let i = 0; i < 32; i++)Loop through each bit position

bitSum += (num >> i) & 1Count set bits at position i

if (bitSum % 3 !== 0)Set bit in result if remainder is 1

⏱

Complexity

TimeO(32 * n) = O(n)

SpaceO(1)

We iterate over 32 bits and for each bit iterate over n numbers, resulting in linear time. Space is constant as only counters and result are used.

💡 For n=100,000, this means about 3.2 million operations, which is efficient for modern computers.

Interview Verdict: Accepted and efficient

This approach is optimal in space and time for this problem and is a common interview solution.

🧠

Finite State Machine Bitwise Solution

💡 This approach uses bitwise operations to simulate a finite state machine tracking bits appearing once and twice, achieving constant space and linear time without explicit bit counting.

Intuition

Use two variables to track bits appearing once and twice. When a bit appears the third time, it resets in both variables, leaving only the unique bits in 'ones'.

Algorithm

1. Initialize two integers ones and twos to 0.
2. For each number in the array:
3. Update twos with bits that have appeared twice.
4. Update ones with bits that have appeared once.
5. Clear bits from ones and twos that have appeared three times.
6. Return ones as the unique number.

💡 This algorithm cleverly uses bitwise AND, OR, and NOT to track bit counts modulo 3 without extra space.

</>

Code

def singleNumber(nums):
    ones = 0
    twos = 0
    for num in nums:
        twos |= ones & num
        ones ^= num
        common_mask = ~(ones & twos)
        ones &= common_mask
        twos &= common_mask
    return ones

# Driver code
if __name__ == '__main__':
    print(singleNumber([2,2,3,2]))  # Output: 3

Line Notes

ones = 0Tracks bits appearing once

twos = 0Tracks bits appearing twice

twos |= ones & numAdd bits appearing second time

ones ^= numToggle bits appearing first time

common_mask = ~(ones & twos)Mask bits appearing third time

ones &= common_maskClear bits appearing third time from ones

twos &= common_maskClear bits appearing third time from twos

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

    public static void main(String[] args) {
        System.out.println(singleNumber(new int[]{2,2,3,2})); // Output: 3
    }
}

Line Notes

int ones = 0, twos = 0Initialize bit trackers for once and twice

twos |= ones & numUpdate twos with bits appearing second time

ones ^= numToggle bits in ones for current number

int commonMask = ~(ones & twos)Mask bits appearing third time

ones &= commonMaskClear bits appearing third time from ones

twos &= commonMaskClear bits appearing third time from twos

#include <iostream>
#include <vector>

using namespace std;

int singleNumber(vector<int>& nums) {
    int ones = 0, twos = 0;
    for (int num : nums) {
        twos |= ones & num;
        ones ^= num;
        int commonMask = ~(ones & twos);
        ones &= commonMask;
        twos &= commonMask;
    }
    return ones;
}

int main() {
    vector<int> nums = {2,2,3,2};
    cout << singleNumber(nums) << endl; // Output: 3
    return 0;
}

Line Notes

int ones = 0, twos = 0Initialize bit counters for once and twice

twos |= ones & numAdd bits appearing second time

ones ^= numToggle bits appearing first time

int commonMask = ~(ones & twos)Mask bits appearing third time

ones &= commonMaskClear bits appearing third time from ones

twos &= commonMaskClear bits appearing third time from twos

function singleNumber(nums) {
    let ones = 0, twos = 0;
    for (const num of nums) {
        twos |= ones & num;
        ones ^= num;
        const commonMask = ~(ones & twos);
        ones &= commonMask;
        twos &= commonMask;
    }
    return ones;
}

// Test
console.log(singleNumber([2,2,3,2])); // Output: 3

Line Notes

let ones = 0, twos = 0Initialize bit trackers for once and twice

twos |= ones & numUpdate twos with bits appearing second time

ones ^= numToggle bits in ones for current number

const commonMask = ~(ones & twos)Mask bits appearing third time

ones &= commonMaskClear bits appearing third time from ones

twos &= commonMaskClear bits appearing third time from twos

⏱

Complexity

TimeO(n)

SpaceO(1)

Single pass through the array with constant extra space using bitwise operations.

💡 For n=100,000, this means 100,000 operations, very efficient and minimal memory usage.

Interview Verdict: Accepted and optimal

This is the most elegant and efficient solution, often preferred in interviews for its clever use of bitwise logic.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, coding the bit counting or FSM approach is preferred for efficiency and elegance. Brute force is good to mention but not to implement.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n)	O(n)	No	Yes	Mention only - never code
2. Bit Counting with Modulo 3	O(n)	O(1)	No	Yes	Good to code for clarity and efficiency
3. Finite State Machine Bitwise	O(n)	O(1)	No	Yes	Best approach to code if comfortable with bitwise logic

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before interviews. Start with brute force to build intuition, then progress to optimal bitwise solutions. Practice explaining each step clearly.

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Describe the brute force approach using a hash map.Step 3: Explain the bit counting with modulo 3 approach for optimization.Step 4: Present the finite state machine bitwise solution as the optimal method.Step 5: Code the chosen approach and test with examples.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 10min → Test: 3min. Total ~20min

What the Interviewer Tests

Interviewer tests your understanding of bit manipulation, ability to optimize space/time, and clarity in explaining complex logic.

Common Follow-ups

• What if every element appears k times except one? → Generalize bit counting modulo k or FSM approach.
• How to handle negative numbers? → Use 32-bit signed integer logic and handle sign bit carefully.

💡 These follow-ups test your ability to generalize solutions and handle edge cases like negative numbers.

🔍

Pattern Recognition

When to Use

1) Array with all elements repeated k times except one; 2) Need to find unique element; 3) Constraints require O(1) space; 4) Bit manipulation hints present.

Signature Phrases

'every element appears three times except one''find the single element''linear runtime and constant space'

NOT This Pattern When

Problems where elements appear twice or no repetition constraints, which can be solved by simple XOR.

Similar Problems

Single Number - simpler version with pairsSingle Number III - two unique numbersSingle Number IV - generalized k times

Practice

1. Identify the bug in the following trie-based maximum XOR code snippet:

medium

A. Line with 'node = node.children[bit]' does not check if 'bit' exists in children.

B. Line with 'if bit not in node.children:' should check for toggled_bit instead.

C. Line with 'max_xor |= (1 << i)' should be outside the if condition.

D. Line with 'node = self.root' should be inside the for loop.

Solution

1. Step 1: Analyze traversal in findMaxXor

   When toggled_bit is not found, code moves to node.children[bit] without checking if bit exists, risking KeyError.

2. Step 2: Identify missing null check

   Should use node.children.get(bit) or check existence before accessing to avoid runtime error.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing check causes crash on inputs missing bit child [OK]

Hint: Always check child existence before traversal [OK]

Common Mistakes:

• Assuming child always exists
• Confusing toggled_bit check
• Misplacing max_xor update

2. The following code attempts to reverse bits of a 32-bit unsigned integer using divide and conquer masks:

def reverseBits(n: int) -> int:
    n = ((n >> 1) & 0x55555555) | ((n & 0x55555555) << 1)
    n = ((n >> 2) & 0x33333333) | ((n & 0x33333333) << 2)
    n = ((n >> 4) & 0x0f0f0f0f) | ((n & 0x0f0f0f0f) << 4)
    n = ((n >> 8) & 0x00ff00ff) | ((n & 0x00ff00ff) << 8)
    n = (n >> 16) | (n << 16)  # Bug here: missing mask
    return n

What is the bug in this code?

medium

A. Line 4: The mask 0x00ff00ff is incorrect for byte swapping.

B. Line 1: Incorrect mask 0x55555555 used for swapping bits.

C. Line 3: Left shift by 4 bits should be right shift.

D. Line 5: Missing mask after shifting left and right by 16 bits, causing overflow beyond 32 bits.

Solution

1. Step 1: Identify the last step

   The last line shifts bits by 16 left and right but does not mask the result to 32 bits.

2. Step 2: Understand impact

   Without masking, bits can overflow beyond 32 bits, causing incorrect reversal results.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Masking with 0xffffffff fixes overflow [OK]

Hint: Always mask after large shifts to keep 32-bit result [OK]

Common Mistakes:

• Forgetting to mask after left shifts
• Misusing masks in earlier steps
• Confusing left and right shifts

3. The following code attempts to find the single number in an array using XOR. Identify the line containing the subtle bug that causes incorrect results.

medium

A. Line 2: Initializing result to nums[0] instead of 0

B. Line 4: Returning result without sorting

C. Line 3: Looping over nums including the first element again

D. Line 1: Function definition

Solution

1. Step 1: Analyze initialization of result

   Result initialized to nums[0], then XORed again with nums[0] in loop, cancelling it out incorrectly.

2. Step 2: Understand correct initialization

   Result should start at 0 so XOR accumulates all elements exactly once.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Initializing to zero avoids double XOR of first element [OK]

Hint: XOR accumulator must start at zero [OK]

Common Mistakes:

• Initializing with first element causes double XOR
• Loop includes first element again
• Misplaced return statement

4. Consider the following buggy UTF-8 validation code snippet. Which line contains the subtle bug that can cause invalid UTF-8 sequences to be accepted as valid?

def validUtf8(data):
    remaining = 0
    for byte in data:
        if remaining == 0:
            if (byte >> 5) == 0b110:
                remaining = 1
            elif (byte >> 4) == 0b1110:
                remaining = 2
            elif (byte >> 3) == 0b11110:
                remaining = 3
            elif (byte >> 7) == 0:
                remaining = 0
            else:
                return False
        else:
            # Bug: missing check for continuation byte pattern
            remaining -= 1
    return remaining == 0

medium

A. Line with 'if remaining == 0:' condition

B. Line with 'remaining -= 1' inside else block

C. Line with 'if (byte >> 5) == 0b110:' condition

D. Line with 'return remaining == 0' at the end

Solution

1. Step 1: Identify where continuation bytes are checked

   The else block handles continuation bytes, which must start with bits '10' (binary 0b10).

2. Step 2: Locate missing validation

   The code decrements remaining without checking if the byte starts with '10', allowing invalid bytes to pass.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Missing continuation byte pattern check causes acceptance of invalid sequences [OK]

Hint: Check continuation bytes start with '10' before decrementing [OK]

Common Mistakes:

• Forgetting continuation byte pattern check
• Miscounting remaining bytes

5. Suppose the input array can contain multiple elements that appear only once, while all others appear twice. Which modification to the XOR approach correctly finds all unique elements?

hard

A. Use XOR as before; it will return the XOR of all unique elements combined

B. Sort the array and scan to find all unique elements by comparing neighbors

C. Use a hash map to count occurrences and collect elements with count 1

D. Apply XOR pairwise on elements and recursively split the array

Solution

1. Step 1: Understand XOR limitation

   XOR of multiple unique elements combined is a single number, not individual uniques.

2. Step 2: Identify approach to find all unique elements

   Counting occurrences with a hash map correctly identifies all unique elements.

3. Step 3: Compare alternatives

   Sorting works but is less efficient; recursive XOR splitting is complex and error-prone.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Hash map approach correctly handles multiple unique elements [OK]

Hint: XOR only isolates one unique element, not multiple [OK]

Common Mistakes:

• Assuming XOR returns all unique elements
• Ignoring multiple unique elements case
• Overcomplicating with recursion