Skip to content

3483. Unique 3-Digit Even Numbers

  • Time: $O(n^3)$
  • Space: $O(n^3)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
 public:
  int totalNumbers(vector<int>& digits) {
    unordered_set<int> nums;
    vector<int> perm = digits;

    ranges::sort(perm);

    do {
      const int a = perm[0];
      const int b = perm[1];
      const int c = perm[2];
      if (a != 0 && c % 2 == 0)
        nums.insert(a * 100 + b * 10 + c);
    } while (next_permutation(perm.begin(), perm.end()));

    return nums.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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
class Solution {
  public int totalNumbers(int[] digits) {
    Set<Integer> nums = new HashSet<>();
    int[] perm = digits.clone();

    Arrays.sort(perm);

    do {
      final int a = perm[0];
      final int b = perm[1];
      final int c = perm[2];
      if (a != 0 && c % 2 == 0) {
        nums.add(a * 100 + b * 10 + c);
      }
    } while (nextPermutation(perm));

    return nums.size();
  }

  private boolean nextPermutation(int[] nums) {
    final int n = nums.length;

    // From the back to the front, find the first num < nums[i + 1].
    int i;
    for (i = n - 2; i >= 0; --i)
      if (nums[i] < nums[i + 1])
        break;

    if (i < 0)
      return false;

    // From the back to the front, find the first num > nums[i] and swap it with
    // nums[i].
    for (int j = n - 1; j > i; --j)
      if (nums[j] > nums[i]) {
        swap(nums, i, j);
        break;
      }

    // Reverse nums[i + 1..n - 1].
    reverse(nums, i + 1, n - 1);
    return true;
  }

  private void reverse(int[] nums, int l, int r) {
    while (l < r)
      swap(nums, l++, r--);
  }

  private void swap(int[] nums, int i, int j) {
    final int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
  }
}

1
2
3
4
5
6
7
8
9
class Solution:
  def totalNumbers(self, digits: list[int]) -> int:
    nums = set()

    for a, b, c in itertools.permutations(digits, 3):
      if a != 0 and c % 2 == 0:
        nums.add(a * 100 + b * 10 + c)

    return len(nums)