The Two Sneaky Numbers of Digitville

Easy
600.

The Two Sneaky Numbers of Digitville

The Two Sneaky Numbers of Digitville is an easy coding problem on arrays and hash table, asked in TCS and Cognizant interviews.

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.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number[]}
 */
var getSneakyNumbers = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

The Two Sneaky Numbers of Digitville — Problem & Solution

The Two Sneaky Numbers of Digitville solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

The Two Sneaky Numbers of Digitville is an easy coding problem on arrays and hash table, asked in TCS and Cognizant interviews.

  • 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.

Hints for The Two Sneaky Numbers of Digitville

  1. Hint 1

    The values are bounded by the array length, which is the signal to count with an array rather than a hash map.

  2. Hint 2

    Tally every value, then report the two whose tally is 2.

  3. Hint 3

    Scanning the tally in index order gives ascending output for free.

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]

Java

public static int[] getSneakyNumbers(int[] nums) {
    int[] count = new int[nums.length];
    for (int x : nums) count[x]++;
    int[] out = new int[2];
    int m = 0;
    for (int v = 0; v < count.length; v++) {
        if (count[v] == 2) out[m++] = v;
    }
    return out;
}

C++

vector<int> getSneakyNumbers(vector<int>& nums) {
    vector<int> count(nums.size(), 0);
    for (int x : nums) count[x]++;
    vector<int> out;
    for (int v = 0; v < (int) count.size(); v++) {
        if (count[v] == 2) out.push_back(v);
    }
    return out;
}

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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets