3483. Unique 3-Digit Even Numbers

Problem Overview

Form distinct three-digit even numbers from a digit multiset.

Intuition

Form distinct three-digit even numbers from a digit multiset. Digits only run from 0 to 9, so count frequencies once, then try every valid hundreds, tens, and even units triple and keep those the bag can supply.

Algorithm

1Build a frequency array of size 10.
2Loop hundreds from 1 to 9, tens from 0 to 9, units over 0,2,4,6,8.
3For each triple, check that needed counts do not exceed available frequencies.
4Count every accepted triple.

Example Walkthrough

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

1.Units must be even, so 2 or 4.
2.Hundreds cannot be 0, and each digit is used at most as often as it appears.
3.Twelve distinct numbers such as 124 and 312 are possible.

Output: 12

Common Pitfalls

•Repeated digits need enough copies in the frequency bag.
•Leading zeros are invalid for a three-digit number.
•Do not permute the full array; frequency checks are enough.
•Units must be even; odds never form a valid answer.

3483.cs

// Approach: Count digit frequencies. Enumerate hundreds (1-9), tens (0-9), and
// even units (0,2,4,6,8). Accept a number when the multiset of used digits is
// covered by the available counts.
// Complexity: O(1) time and O(1) extra space (fixed 10-digit alphabet).
public class Solution
{
    public int TotalNumbers(int[] digits)
    {
        int[] freq = new int[10];
        foreach (int d in digits)
            freq[d]++;

        int ans = 0;
        for (int hundreds = 1; hundreds <= 9; hundreds++)
        {
            for (int tens = 0; tens <= 9; tens++)
            {
                for (int units = 0; units <= 8; units += 2)
                {
                    if (CanForm(freq, hundreds, tens, units))
                        ans++;
                }
            }
        }

        return ans;
    }

    private bool CanForm(int[] freq, int a, int b, int c)
    {
        int[] need = new int[10];
        need[a]++;
        need[b]++;
        need[c]++;

        for (int d = 0; d < 10; d++)
            if (need[d] > freq[d])
                return false;

        return true;
    }
}

Was this solution helpful?