Finding 3-Digit Even Numbers — Problem & Solution
Finding 3-Digit Even Numbers solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Finding 3-Digit Even Numbers is an easy coding problem on arrays, hash table and sorting, asked in Amazon and Google interviews.
- Difficulty: Easy
- Topics: Arrays, Hash Table, Sorting, Enumeration
- Asked at: Amazon, Google
- 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
digits is a list of decimal digits that may repeat. Build integers by choosing three different positions of digits and writing their digits in any order, subject to:
- the integer has no leading zero (so it really has three digits), and
- the integer is even.
Return every distinct integer that can be built this way, sorted in ascending order.
Example 1
Input: digits = [4,0,4]
Output: [404,440]
Example 2
Input: digits = [1,3,5]
Output: []
Explanation: No even digit is available for the last place.
Example 3
Input: digits = [6,1,6,0]
Output: [106,160,166,606,610,616,660]
Constraints
3 <= digits.length <= 1000 <= digits[i] <= 9
Hints for Finding 3-Digit Even Numbers
Hint 1
There are only 450 even three-digit numbers: 100, 102, ..., 998.
Hint 2
A candidate can be built when, for each digit, it uses that digit no more often than
digitscontains it.Hint 3
Count the digits once, then test each even number from 100 to 998 against the counts — the output comes out sorted for free.
How to solve Finding 3-Digit Even Numbers
Instead of combining positions (up to 100^3 triples), enumerate the answers: test each of the 450 even three-digit numbers against the digit counts.
Approach
- Count how many times each digit 0–9 occurs in
digits. - For
xfrom 100 to 998 in steps of 2, split it into its three digits. - Keep
xif, after taking those three digits from the counts, no count is negative; restore the counts afterwards. - The kept numbers are already in ascending order.
Why it works
A number can be formed from three distinct positions exactly when the multiset of its digits fits inside the multiset of digits. Starting at 100 rules out leading zeros, and stepping by 2 from an even start keeps only even numbers, so the scan produces precisely the required set, once each, in order.
Complexity
- Time —
O(n + 450) - Space —
O(1)
Pitfalls
- A digit may be used only as many times as it occurs:
[2,2,8]can make 282 but not 222. - Duplicates in
digitsproduce the same number many ways — report each number once. - Leading zeros are not allowed:
[0,2,4]gives 204, 240, 402, 420, but not 024.
Reference solution
Python
from typing import List
def findEvenNumbers(digits: List[int]) -> List[int]:
cnt = [0] * 10
for d in digits:
cnt[d] += 1
out = []
for x in range(100, 1000, 2):
a, b, c = x // 100, x // 10 % 10, x % 10
cnt[a] -= 1
cnt[b] -= 1
cnt[c] -= 1
if cnt[a] >= 0 and cnt[b] >= 0 and cnt[c] >= 0:
out.append(x)
cnt[a] += 1
cnt[b] += 1
cnt[c] += 1
return outJava
public static int[] findEvenNumbers(int[] digits) {
int[] cnt = new int[10];
for (int d : digits) cnt[d]++;
List<Integer> out = new ArrayList<>();
for (int x = 100; x < 1000; x += 2) {
int a = x / 100, b = x / 10 % 10, c = x % 10;
cnt[a]--; cnt[b]--; cnt[c]--;
if (cnt[a] >= 0 && cnt[b] >= 0 && cnt[c] >= 0) out.add(x);
cnt[a]++; cnt[b]++; cnt[c]++;
}
int[] res = new int[out.size()];
for (int i = 0; i < res.length; i++) res[i] = out.get(i);
return res;
}C++
vector<int> findEvenNumbers(vector<int>& digits) {
int cnt[10] = { 0 };
for (int d : digits) cnt[d]++;
vector<int> out;
for (int x = 100; x < 1000; x += 2) {
int a = x / 100, b = x / 10 % 10, c = x % 10;
cnt[a]--; cnt[b]--; cnt[c]--;
if (cnt[a] >= 0 && cnt[b] >= 0 && cnt[c] >= 0) out.push_back(x);
cnt[a]++; cnt[b]++; cnt[c]++;
}
return out;
}JavaScript
var findEvenNumbers = function(digits) {
var cnt = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0];
for (var i = 0; i < digits.length; i++) cnt[digits[i]]++;
var out = [];
for (var x = 100; x < 1000; x += 2) {
var a = Math.floor(x / 100), b = Math.floor(x / 10) % 10, c = x % 10;
cnt[a]--; cnt[b]--; cnt[c]--;
if (cnt[a] >= 0 && cnt[b] >= 0 && cnt[c] >= 0) out.push(x);
cnt[a]++; cnt[b]++; cnt[c]++;
}
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