Finding 3-Digit Even Numbers

Easy
1118.

Finding 3-Digit Even Numbers

Finding 3-Digit Even Numbers is an easy coding problem on arrays, hash table and sorting, asked in Amazon and Google interviews.

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 <= 100
  • 0 <= digits[i] <= 9
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[]} digits
 * @return {number[]}
 */
var findEvenNumbers = function(digits) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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 <= 100
  • 0 <= digits[i] <= 9

Hints for Finding 3-Digit Even Numbers

  1. Hint 1

    There are only 450 even three-digit numbers: 100, 102, ..., 998.

  2. Hint 2

    A candidate can be built when, for each digit, it uses that digit no more often than digits contains it.

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

  1. Count how many times each digit 0–9 occurs in digits.
  2. For x from 100 to 998 in steps of 2, split it into its three digits.
  3. Keep x if, after taking those three digits from the counts, no count is negative; restore the counts afterwards.
  4. 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 digits produce 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 out

Java

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