Single Number II (Three Copies)

📋

Problem

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.

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.

Edge cases: Array with only one element → returns that elementAll elements are negative except the unique one → returns unique correctlyUnique element is zero → returns zero

</>

IDE

def singleNumber(nums: list[int]) -> int:public int singleNumber(int[] nums)int singleNumber(vector<int>& nums)function singleNumber(nums)

def singleNumber(nums):
    # Write your solution here
    pass

class Solution {
    public int singleNumber(int[] nums) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int singleNumber(vector<int>& nums) {
    // Write your solution here
    return 0;
}

function singleNumber(nums) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: 0Returning 0 when unique number is negative or non-zero due to incorrect bit reconstruction.✅ Properly reconstruct signed integer from bit counts using two's complement logic.

Wrong: First non-triplet number encounteredUsing a greedy approach that picks first number not repeated thrice without bit counting.✅ Implement bit counting with modulo 3 to isolate unique number bits.

Wrong: Wrong unique number when multiple triplets existNot aggregating bit counts over all triplets before modulo operation.✅ Sum bits for all numbers before applying modulo 3.

Wrong: Timeout or memory errorUsing hash maps or sorting leading to O(n) space or O(n log n) time.✅ Use bitwise counting with modulo 3 for O(n) time and O(1) space.

✓

Test Cases

Try testing your solution on single element and negative number inputs.

Consider tricky cases with multiple triplets and greedy traps.

Optimize your solution to run efficiently on large inputs using bitwise operations.

t1_01basic

Input{"nums":[2,2,3,2]}

Expected3

⏱ Performance - must finish in 2000ms

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

💡 Consider counting bits at each position across all numbers.

💡 Use modulo 3 on bit counts to isolate the unique number's bits.

💡 Reconstruct the unique number from bits where count mod 3 is 1.

Why it failed: Incorrect output means bit counting or modulo logic is wrong; ensure you count bits for all 32 positions and apply modulo 3 correctly.

✓ Correctly identifies the unique number using bit counting and modulo 3.

t1_02basic

Input{"nums":[0,1,0,1,0,1,99]}

Expected99

⏱ Performance - must finish in 2000ms

0 and 1 appear three times each; 99 appears once and is returned.

💡 Check how zero bits affect the counting and modulo operation.

💡 Verify that bits from all numbers including zero are counted properly.

💡 Ensure the final number is reconstructed correctly from bit counts mod 3.

Why it failed: Failing here indicates mishandling of zero or multiple repeated numbers; fix bit counting and modulo aggregation.

✓ Handles zero and multiple triplets correctly to find the unique number.

t2_01edge

Input{"nums":[7]}

Expected7

⏱ Performance - must finish in 2000ms

Single element array returns that element as unique.

💡 Test the base case where array length is 1.

💡 Ensure your code handles arrays without triplets gracefully.

💡 Return the single element directly if no triplets exist.

Why it failed: Fails single element case by assuming triplets exist; add base case handling for length 1.

✓ Correctly returns the single element when array length is 1.

t2_02edge

Input{"nums":[-1,-1,-1,-50]}

Expected-50

⏱ Performance - must finish in 2000ms

All elements except -50 appear three times; negative numbers handled correctly.

💡 Check that negative numbers are handled correctly in bitwise operations.

💡 Remember to treat bits as signed 32-bit integers when reconstructing.

💡 Use two's complement logic to reconstruct negative unique number.

Why it failed: Fails negative unique number due to incorrect sign bit handling; fix bit reconstruction for signed integers.

✓ Correctly identifies negative unique number using proper bitwise sign handling.

t2_03edge

Input{"nums":[0,0,0,99]}

Expected99

⏱ Performance - must finish in 2000ms

Unique element is zero in triplets, unique number is 99.

💡 Verify that zero bits in triplets do not affect unique number detection.

💡 Ensure modulo 3 counting excludes triplet bits correctly.

💡 Rebuild unique number bits accurately even when zero is repeated.

Why it failed: Fails when zero is repeated triplet due to incorrect bit counting; fix modulo logic to exclude triplet bits.

✓ Handles zero triplets and unique number correctly.

t3_01corner

Input{"nums":[5,5,5,7,7,7,9]}

Expected9

⏱ Performance - must finish in 2000ms

Multiple triplets with unique number 9; tests correct aggregation of multiple triplets.

💡 Check that your solution does not confuse multiple triplets with the unique number.

💡 Verify bit counts aggregate all triplets before modulo operation.

💡 Ensure unique number bits are isolated after removing all triplet contributions.

Why it failed: Fails to separate multiple triplets from unique number; fix bit counting to sum all triplets before modulo.

✓ Correctly isolates unique number despite multiple triplets.

t3_02corner

Input{"nums":[10,10,10,10,10,10,11]}

Expected11

⏱ Performance - must finish in 2000ms

Tests that solution does not assume exactly three copies but handles only triplets; here 10 appears six times (two triplets).

💡 Confirm your solution works when triplets appear multiple times (e.g., 6 times = 2 triplets).

💡 Count bits cumulatively and apply modulo 3 to handle multiple triplets.

💡 Do not assume only one triplet per number; aggregate all occurrences.

Why it failed: Fails when triplets appear multiple times due to incorrect modulo application; fix to apply modulo 3 on total bit counts.

✓ Handles multiple triplets of same number correctly.

t3_03corner

Input{"nums":[1,1,1,2,2,2,3,3,3,4]}

Expected4

⏱ Performance - must finish in 2000ms

Greedy approach trap: picking first non-triplet number fails; must count bits properly.

💡 Avoid greedy approaches that pick first non-triplet number encountered.

💡 Use bitwise counting and modulo 3 to find unique number.

💡 Rebuild unique number from bits where count mod 3 is 1, not by scanning array greedily.

Why it failed: Fails due to greedy approach picking wrong unique number; fix to use bit counting and modulo 3 logic.

✓ Correctly finds unique number using bitwise counting, avoiding greedy traps.

t4_01performance

Input{"nums":[42,42,42,17,17,17,99,99,99,123,123,123,7,7,7,0,0,0,1,1,1,2,2,2,3,3,3,4,4,4,5,5,5,6,6,6,8,8,8,9,9,9,10,10,10,11,11,11,12,12,12,13,13,13,14,14,14,15,15,15,16,16,16,18,18,18,19,19,19,20,20,20,21,21,21,22,22,22,23,23,23,24,24,24,25,25,25,26,26,26,27,27,27,28,28,28,29,29,29,30,30,30,31,31,31,32,32,32,33,33,33,34,34,34,35,35,35,36,36,36,37,37,37,38,38,38,39,39,39,40,40,40,41,41,41,43,43,43,44,44,44,45,45,45,46,46,46,47,47,47,48,48,48,49,49,49,50,50,50,51,51,51,52,52,52,53,53,53,54,54,54,55,55,55,56,56,56,57,57,57,58,58,58,59,59,59,60,60,60,61,61,61,62,62,62,63,63,63,64,64,64,65,65,65,66,66,66,67,67,67,68,68,68,69,69,69,70,70,70,71,71,71,72,72,72,73,73,73,74,74,74,75,75,75,76,76,76,77,77,77,78,78,78,79,79,79,80,80,80,81,81,81,82,82,82,83,83,83,84,84,84,85,85,85,86,86,86,87,87,87,88,88,88,89,89,89,90,90,90,91,91,91,92,92,92,93,93,93,94,94,94,95,95,95,96,96,96,97,97,97,98,98,98,100]}

Expectednull

⏱ Performance - must finish in 2000ms

Large input with n=100, multiple triplets and one unique number 100; solution must run in O(n) time within 2 seconds.

💡 Use bitwise counting with modulo 3 for O(n) time and O(1) space.

💡 Avoid hash maps or sorting which increase time or space complexity.

💡 Implement finite state machine bitwise solution for optimal performance.

Why it failed: TLE indicates use of brute force or hash map with O(n) space or worse; fix to O(n) time and O(1) space bitwise solution.

✓ Solution runs in linear time with constant space as required.

Practice

1. Consider the following Python function to find two missing numbers from 1 to n using XOR partitioning. Given n = 4 and arr = [1, 3], what is the final returned list?

easy

A. [4, 2]

B. [1, 3]

C. [2, 4]

D. [3, 1]

Solution

1. Step 1: Compute xor_all

   xor_all = 1^2^3^4 ^ 1^3 = (1^1)^(2)^(3^3)^(4) = 2 ^ 4 = 6 (binary 110)

2. Step 2: Find rightmost set bit and partition

   set_bit = 6 & (-6) = 2 (binary 010). Partition numbers by this bit: Group 1 (bit set): numbers with bit 2 set -> 2, 3 Group 2 (bit not set): 1, 4 XOR group 1: 2 ^ 3 ^ (arr nums with bit set: 3) = 2 ^ 3 ^ 3 = 2 XOR group 2: 1 ^ 4 ^ (arr nums with bit not set: 1) = 1 ^ 4 ^ 1 = 4 So missing numbers are [2, 4].

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Output matches expected missing numbers [OK]

Hint: Trace XOR and partition by rightmost set bit carefully [OK]

Common Mistakes:

• Misinterpret bit masking for partition
• Mixing order of XOR operations
• Confusing missing numbers with present ones

2. Given the following Python function for UTF-8 validation, what is the value of the variable remaining after processing the second byte in the input [197, 130, 1]?

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:
            if (byte >> 6) != 0b10:
                return False
            remaining -= 1
    return remaining == 0

easy

A. 2

B. 0

C. 1

D. False (function returns early)

Solution

1. Step 1: Trace first byte (197)

   197 in binary is 11000101. (197 >> 5) == 0b110, so remaining is set to 1.

2. Step 2: Trace second byte (130)

   Since remaining is 1, check if (130 >> 6) == 0b10. 130 in binary is 10000010, so condition holds and remaining is decremented to 0.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Remaining after second byte is 1 -> decremented to 0 after processing second byte [OK]

Hint: Check bit shifts and decrement continuation counter correctly [OK]

Common Mistakes:

• Off-by-one decrement of remaining
• Misinterpreting bit shifts for continuation bytes

3. The following code attempts to find the missing number using XOR. Which line contains the subtle bug that causes incorrect results when the missing number is n?

medium

A. Line 3: initializing xor_all to 0

B. Line 7: returning xor_all without modification

C. Line 4: iterating only to n-1 instead of n

D. Line 6: XORing array elements

Solution

1. Step 1: Analyze the loop range for XORing indices

   The loop runs from 0 to n-1 (range(n)), missing the number n itself.

2. Step 2: Understand impact on missing number detection

   Since n is not XORed, if n is the missing number, it won't be accounted for, causing wrong output.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Changing loop to range(n+1) fixes the bug [OK]

Hint: Loop must include n to XOR all indices correctly [OK]

Common Mistakes:

• Off-by-one in loop range
• Forgetting to XOR n
• Assuming initialization causes bug

4. Consider the following buggy code for generating subsets. Which line contains the subtle bug that causes all subsets in res to be the same list instance?

medium

A. Line 4: def backtrack(start, path):

B. Line 7: path.append(nums[i])

C. Line 5: res.append(path)

D. Line 9: path.pop()

Solution

1. Step 1: Identify how subsets are added to results

   Appending path directly adds a reference, not a copy, so all entries point to the same list object.

2. Step 2: Fix by appending a copy of path

   Using path[:] or list(path) creates a snapshot copy, preserving each subset uniquely.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Appending reference causes all subsets to be identical [OK]

Hint: Always append a copy of the current path [OK]

Common Mistakes:

• Appending mutable list reference instead of a copy

5. If the input number n can be negative or zero, and you want to check if its absolute value is a power of four, which modification to the optimal logarithm-based approach is correct?

hard

A. Remove the check for n <= 0 and directly compute log2(n)/2

B. Add a check to return False if n is zero or negative before applying logarithm on abs(n)

C. Use the brute force iterative division approach instead, as logarithm fails for negative inputs

D. Take the absolute value of n before the logarithm check and keep the rest unchanged

Solution

1. Step 1: Consider input domain

   Since n can be zero or negative, these are not powers of four, so must return False immediately.

2. Step 2: Apply logarithm check on absolute value

   After filtering invalid inputs, apply logarithm on abs(n) to check power of four.

3. Step 3: Finalize correct approach

   Adding a check to return False for zero or negative inputs before log check ensures correctness and avoids math domain errors.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Zero and negatives are filtered out before log check on abs(n) [OK]

Hint: Filter invalid inputs before log check on abs(n)

Common Mistakes:

• Removing input validation
• Applying log on negative numbers causing errors