Skip to content

3483. Unique 3-Digit Even Numbers

Description

You are given an array of digits called digits. Your task is to determine the number of distinct three-digit even numbers that can be formed using these digits.

Note: Each copy of a digit can only be used once per number, and there may not be leading zeros.

 

Example 1:

Input: digits = [1,2,3,4]

Output: 12

Explanation: The 12 distinct 3-digit even numbers that can be formed are 124, 132, 134, 142, 214, 234, 312, 314, 324, 342, 412, and 432. Note that 222 cannot be formed because there is only 1 copy of the digit 2.

Example 2:

Input: digits = [0,2,2]

Output: 2

Explanation: The only 3-digit even numbers that can be formed are 202 and 220. Note that the digit 2 can be used twice because it appears twice in the array.

Example 3:

Input: digits = [6,6,6]

Output: 1

Explanation: Only 666 can be formed.

Example 4:

Input: digits = [1,3,5]

Output: 0

Explanation: No even 3-digit numbers can be formed.

 

Constraints:

  • 3 <= digits.length <= 10
  • 0 <= digits[i] <= 9

Solutions

Solution 1: Hash Set + Enumeration

Thinking

We form three-digit even numbers from at most \(10\) digits with distinct indices, and count distinct values. \(n^3\le 10^3\), so a triple loop is enough.

The ones digit must be even, the hundreds digit cannot be \(0\), and the three indices are distinct. A set collapses different index triples that yield the same number.

Enumerate an even ones digit \(a\), then tens \(b\) and hundreds \(c\), and insert \(100c+10b+a\).

We use a hash set \(\textit{s}\) to record all distinct three-digit even numbers, and then enumerate all possible three-digit even numbers to add them to the hash set.

Finally, we return the size of the hash set.

The time complexity is \(O(n^3)\), and the space complexity is \(O(n^3)\). Where \(n\) is the length of the array \(\textit{digits}\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
    def totalNumbers(self, digits: List[int]) -> int:
        s = set()
        for i, a in enumerate(digits):
            if a & 1:
                continue
            for j, b in enumerate(digits):
                if i == j:
                    continue
                for k, c in enumerate(digits):
                    if c == 0 or k in (i, j):
                        continue
                    s.add(c * 100 + b * 10 + a)
        return len(s)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int totalNumbers(int[] digits) {
        Set<Integer> s = new HashSet<>();
        int n = digits.length;
        for (int i = 0; i < n; ++i) {
            if (digits[i] % 2 == 1) {
                continue;
            }
            for (int j = 0; j < n; ++j) {
                if (i == j) {
                    continue;
                }
                for (int k = 0; k < n; ++k) {
                    if (digits[k] == 0 || k == i || k == j) {
                        continue;
                    }
                    s.add(digits[k] * 100 + digits[j] * 10 + digits[i]);
                }
            }
        }
        return s.size();
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int totalNumbers(vector<int>& digits) {
        unordered_set<int> s;
        int n = digits.size();
        for (int i = 0; i < n; ++i) {
            if (digits[i] % 2 == 1) {
                continue;
            }
            for (int j = 0; j < n; ++j) {
                if (i == j) {
                    continue;
                }
                for (int k = 0; k < n; ++k) {
                    if (digits[k] == 0 || k == i || k == j) {
                        continue;
                    }
                    s.insert(digits[k] * 100 + digits[j] * 10 + digits[i]);
                }
            }
        }
        return s.size();
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
func totalNumbers(digits []int) int {
    s := make(map[int]struct{})
    for i, a := range digits {
        if a%2 == 1 {
            continue
        }
        for j, b := range digits {
            if i == j {
                continue
            }
            for k, c := range digits {
                if c == 0 || k == i || k == j {
                    continue
                }
                s[c*100+b*10+a] = struct{}{}
            }
        }
    }
    return len(s)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
function totalNumbers(digits: number[]): number {
    const s = new Set<number>();
    const n = digits.length;
    for (let i = 0; i < n; ++i) {
        if (digits[i] % 2 === 1) {
            continue;
        }
        for (let j = 0; j < n; ++j) {
            if (i === j) {
                continue;
            }
            for (let k = 0; k < n; ++k) {
                if (digits[k] === 0 || k === i || k === j) {
                    continue;
                }
                s.add(digits[k] * 100 + digits[j] * 10 + digits[i]);
            }
        }
    }
    return s.size;
}

Comments