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 <= 100nums.length == n + 20 <= nums[i] <= n - 1Exactly two values occur twice; every other value occurs once.
Hints for The Two Sneaky Numbers of Digitville
Hint 1
The values are bounded by the array length, which is the signal to count with an array rather than a hash map.
Hint 2
Tally every value, then report the two whose tally is 2.
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
- Allocate
countof lengthn + 2(any size at leastnworks) filled with zeros. - For each
xinnums, incrementcount[x]. - Scan
countfrom0upward and collect every index whose tally is2.
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 nfactor 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