The Two Sneaky Numbers of Digitville

Difficulty: Easy | Acceptance: 89.80% | Paid: No Topics: Array, Hash Table, Math

In Digitville, there was a list of numbers from 0 to n - 1 where each number appeared exactly once. The whole list was then shuffled and two numbers were accidentally added twice, making the list length n + 1. Your task is to find and return the two numbers that appear twice in the list.

Given an integer array nums of length n + 1 where 0 <= nums[i] < n, return the two numbers that appear twice in nums. You may return the answer in any order.

• Examples
• Constraints
• Hash Set Approach
• Sorting Approach
• Mathematical Approach
• Bit Manipulation Approach

Examples

Example 1:

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

Example 2:

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

Example 3:

Input: nums = [7,1,5,4,3,6,0,2,2,7] Output: [2,7]

Constraints

2 <= n <= 100
nums.length == n + 1
0 <= nums[i] < n
The input is generated such that exactly two numbers appear twice and all other numbers appear exactly once.

Hash Set Approach

Intuition Use a hash set to track numbers we’ve seen. When we encounter a number already in the set, it’s a duplicate.

Steps

• Initialize an empty set and an empty result list
• Iterate through each number in the array
• If the number is already in the set, add it to the result
• Otherwise, add the number to the set
• Return the result when it has two elements

from typing import List

class Solution:
    def getSneakyNumbers(self, nums: List[int]) -> List[int]:
        seen = set()
        result = []
        for num in nums:
            if num in seen:
                result.append(num)
                if len(result) == 2:
                    return result
            seen.add(num)
        return result

Complexity

• Time: O(n)
• Space: O(n)
• Notes: Simple and intuitive, but uses extra space for the set.

Sorting Approach

Intuition Sort the array so that duplicates become adjacent. Then scan to find adjacent equal elements.

Steps

• Sort the array
• Iterate through the array
• If the current element equals the previous element, it’s a duplicate
• Add duplicates to the result
• Return the result when it has two elements

from typing import List

class Solution:
    def getSneakyNumbers(self, nums: List[int]) -> List[int]:
        nums.sort()
        result = []
        for i in range(1, len(nums)):
            if nums[i] == nums[i-1]:
                result.append(nums[i])
                if len(result) == 2:
                    return result
        return result

Complexity

• Time: O(n log n)
• Space: O(1) or O(n) depending on the sorting algorithm
• Notes: No extra space needed (aside from sorting), but slower due to sorting.

Mathematical Approach

Intuition Use the sum and sum of squares to form equations and solve for the two duplicate numbers.

Steps

• Calculate the sum of all elements and the sum of squares of all elements
• Calculate the expected sum and sum of squares for numbers 0 to n-2
• Compute the differences to get a + b and a² + b²
• Use these to find ab
• Solve the quadratic equation to find a and b

from typing import List

class Solution:
    def getSneakyNumbers(self, nums: List[int]) -> List[int]:
        n = len(nums) - 1
        total = sum(nums)
        total_sq = sum(x * x for x in nums)
        
        expected = (n - 2) * (n - 1) // 2
        expected_sq = (n - 2) * (n - 1) * (2 * n - 3) // 6
        
        sum_diff = total - expected
        sum_sq_diff = total_sq - expected_sq
        
        ab = (sum_diff * sum_diff - sum_sq_diff) // 2
        
        discriminant = sum_diff * sum_diff - 4 * ab
        sqrt_discriminant = int(discriminant ** 0.5)
        
        a = (sum_diff + sqrt_discriminant) // 2
        b = (sum_diff - sqrt_discriminant) // 2
        
        return [a, b]

Complexity

• Time: O(n)
• Space: O(1)
• Notes: Constant space, but requires careful handling of large numbers to avoid overflow.

Bit Manipulation Approach

Intuition Use XOR properties to find the two duplicate numbers without extra space.

Steps

• XOR all elements in the array to get XOR of (0 to n-2) except a and b
• XOR this with XOR of 0 to n-2 to get a XOR b
• Find a set bit in a XOR b
• Compute XOR of all numbers from 0 to n-2 with that bit set
• Compute XOR of all elements in the array with that bit set
• XOR these two results to get one of the duplicate numbers
• XOR with a XOR b to get the other duplicate number

from typing import List

class Solution:
    def getSneakyNumbers(self, nums: List[int]) -> List[int]:
        n = len(nums) - 1
        
        xor_array = 0
        for num in nums:
            xor_array ^= num
        
        xor_range = 0
        for i in range(n - 1):
            xor_range ^= i
        
        xor_ab = xor_array ^ xor_range
        
        rightmost_bit = xor_ab & -xor_ab
        
        xor_range_bit = 0
        for i in range(n - 1):
            if i & rightmost_bit:
                xor_range_bit ^= i
        
        xor_array_bit = 0
        for num in nums:
            if num & rightmost_bit:
                xor_array_bit ^= num
        
        a = xor_range_bit ^ xor_array_bit
        b = a ^ xor_ab
        
        return [a, b]

Complexity

• Time: O(n)
• Space: O(1)
• Notes: Constant space and efficient, but more complex to understand and implement.