3483 LeetCode problem solution

LeetCode problem link: 3483. Unique 3-Digit Even Numbers


LeetCode 3483 problem 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 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

LeetCode 3483 problem: solution explanation

The simplest and obviously approach here is brute force over three positions.

Because of the constraints, we can iterate over all triples of indices i, j, and k.


Conditions:

  • i, j, and k must be different;
  • the first digit cannot be 0;
  • the last digit must be even;
  • the numbers must be counted as distinct, so it is convenient to store them in a set.

The set is necessary because, for example, if digits = [1, 1, 2], the same number 112 can be formed using different copies of the first 1, but it should be counted only once.


But, in this solution we will have O(n3) Time complexity. Obviously, this is not good.


LeetCode 3483 C++ O(n3) solution

class Solution {
public:
  int totalNumbers(vector<int>& digits) {
    unordered_set<int> nums;
    int n = digits.size();

    for(int i = 0; i < n; i++)
    {
      if(digits[i] == 0) continue;

      for(int j = 0; j < n; j++)
      {
        if (j == i) continue;

        for(int k = 0; k < n; k++)
        {
          if(k == i || k == j) continue;
          if(digits[k] % 2 != 0) continue;

          int number = digits[i] * 100 + digits[j] * 10 + digits[k];

          nums.insert(number);
        }
      }
    }

    return nums.size();
  }
};

The O(n3) approach can be improved.

Since the digits are limited to 0..9, it is better to switch from indices to a frequency array count[d] for counting how many times digit d appears in digits.
Then, instead of iterating over all triples of indices, we iterate over all possible 3-digit even numbers 100 ... 998 and check whether digits contains enough copies of each required digit.


Time complexity: O(n)
Space complexity: O(1)


LeetCode 3483 C++ O(n) solution

class Solution {
public:
  int totalNumbers(vector<int>& digits) {
    int count[10] = {};
    int res = 0;

    for(int d : digits) count[d]++;

    for(int num = 100; num <= 998; num += 2)
    {
      int a = num / 100;
      int b = (num / 10) % 10;
      int c = num % 10;

      int need[10] = {};
      need[a]++;
      need[b]++;
      need[c]++;

      bool possible = true;

      for(int d = 0; d < 10; d++)
      {
        if(need[d] > count[d])
        {
          possible = false;
          break;
        }
      }

      if(possible) res++;
    }

    return res;
  }
};

LeetCode 3483 Java solution

class Solution {
  public int totalNumbers(int[] digits) {
    int[] count = new int[10];

    for(int d : digits) count[d]++;

    int res = 0;

    for(int num = 100; num <= 998; num += 2) {
      int a = num / 100;
      int b = (num / 10) % 10;
      int c = num % 10;

      int[] need = new int[10];
      need[a]++;
      need[b]++;
      need[c]++;

      boolean possible = true;

      for(int d = 0; d < 10; d++) {
        if(need[d] > count[d]) {
          possible = false;
          break;
        }
      }

      if(possible) res++;
    }

    return res;
  }
}

LeetCode 3483 JavaScript solution

var totalNumbers = function(digits) {
  const count = new Array(10).fill(0);

  for(const d of digits) count[d]++;

  let res = 0;

  for(let num = 100; num <= 998; num += 2) {
    const a = Math.floor(num / 100);
    const b = Math.floor(num / 10) % 10;
    const c = num % 10;

    const need = new Array(10).fill(0);
    need[a]++;
    need[b]++;
    need[c]++;

    let possible = true;

    for(let d = 0; d < 10; d++) {
      if(need[d] > count[d]) {
        possible = false;
        break;
      }
    }

    if(possible) res++;
  }

  return res;
};

LeetCode 3483 TypeScript solution

function totalNumbers(digits: number[]): number {
  const count: number[] = new Array(10).fill(0);

  for(const d of digits) count[d]++;

  let res = 0;

  for(let num = 100; num <= 998; num += 2) {
    const a = Math.floor(num / 100);
    const b = Math.floor(num / 10) % 10;
    const c = num % 10;

    const need: number[] = new Array(10).fill(0);
    need[a]++;
    need[b]++;
    need[c]++;

    let possible = true;

    for(let d = 0; d < 10; d++) {
      if(need[d] > count[d]) {
        possible = false;
        break;
      }
    }

    if(possible) res++;
  }

  return res;
}

LeetCode 3483 Python solution

class Solution:
  def totalNumbers(self, digits: List[int]) -> int:
    count = [0] * 10

    for d in digits:
      count[d] += 1

    res = 0

    for num in range(100, 999, 2):
      a = num // 100
      b = (num // 10) % 10
      c = num % 10

      need = [0] * 10
      need[a] += 1
      need[b] += 1
      need[c] += 1

      possible = True

      for d in range(10):
        if need[d] > count[d]:
          possible = False
          break

      if possible: 
          res += 1

    return res