Get started

The Two Sneaky Numbers of Digitville — Easy Problem & Solution

The registry of Digitville was supposed to list every number from 0 to n - 1 exactly once.

  • Difficulty: Easy
  • Topics: Arrays, Hash Table
  • Asked at: TCS, Cognizant
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

The registry of Digitville was supposed to list every number from 0 to n - 1 exactly once. Instead the list nums has length n + 2: two of the numbers sneaked in a second time.

Return the two repeated numbers in ascending order.

Example 1

Input: nums = [0,1,1,0]
Output: [0,1]
Explanation: n is 2, so 0 and 1 should each appear once — both appear twice.

Example 2

Input: nums = [0,3,2,1,3,2]
Output: [2,3]
Explanation: n is 4; 2 and 3 are the repeats.

Example 3

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

Constraints

  • 2 <= n <= 100
  • nums.length == n + 2
  • 0 <= nums[i] <= n - 1
  • Exactly two values occur twice; every other value occurs once.

How to solve The Two Sneaky Numbers of Digitville

Because the values are exactly 0 .. n - 1, a value is its own index into a counting array — no hashing is needed at all.

Approach

  1. Allocate count of length n + 2 (any size at least n works) filled with zeros.
  2. For each x in nums, increment count[x].
  3. Scan count from 0 upward and collect every index whose tally is 2.

Why it works

Every legal value appears once except the two sneaks, so a tally of 2 identifies exactly the repeats. Scanning indices in increasing order means the result is already sorted.

Complexity

  • Time — O(n)
  • Space — O(n)

Pitfalls

  • Sorting and comparing neighbours also works but costs an extra log n factor for nothing.
  • Using a hash map and iterating it gives an arbitrary order — the answer must be ascending.

Reference solution

Python

from typing import List

def getSneakyNumbers(nums: List[int]) -> List[int]:
    count = [0] * len(nums)
    for x in nums:
        count[x] += 1
    return [v for v in range(len(count)) if count[v] == 2]

JavaScript

var getSneakyNumbers = function(nums) {
    var count = [];
    for (var i = 0; i < nums.length; i++) count.push(0);
    for (var j = 0; j < nums.length; j++) count[nums[j]]++;
    var out = [];
    for (var v = 0; v < count.length; v++) {
        if (count[v] === 2) out.push(v);
    }
    return out;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue