Skip to content

← leetcode

Finding 3 Digit Even Numbers

· Easy

LeetCode problem 2094

Since the solution space is quite small (only a maximum of 449 possible solutions), you can just brute-force this with a recursive function.

I basically just iterated through all the possible 3 digit numbers (using a hash-map to keep track of numbers). Then, if it is even, I just add it to my ans vector.

Finally, since my recursive function always iterates from 0 to 9 at each stage, when we end up pushing digits to the ans vector, they will always be sorted.

code

class Solution {
public:
    void recursiveDigits(vector<int>& digits, vector<int>& mp, vector<int>& ans, int curr) {
        if (curr >= 100) {
            if (curr % 2 == 0) ans.push_back(curr);
            return;
        }
        for (int i = 0; i < 10; ++i) {
            if (i == 0 && curr == 0) continue;
            if (mp[i] > 0) {
                --mp[i];
                curr = curr * 10 + i;
                recursiveDigits(digits, mp, ans, curr);
                curr /= 10;
                ++mp[i];
            }
        }
    }
    vector<int> findEvenNumbers(vector<int>& digits) {
        vector<int> ans;
        vector<int> mp(10, 0);
        for (int& i : digits) {
            ++mp[i];
        }
        recursiveDigits(digits, mp, ans, 0);
        return ans;
    }
};

complexity

  • Time: O(n) where n is the size of the array digits
  • Space: O(1) (cuz technically, I am only always storing a vector of size 10)

time taken

  • unfortunately, due to some bugs, I am ending with a sloppy 10 minutes and 51 seconds