Today I have done leetcode's May LeetCoding Challenge with cpp.

May LeetCoding Challenge 12

Description

Finding 3-Digit Even Numbers

You are given an integer array digits, where each element is a digit. The array may contain duplicates.

You need to find all the unique integers that follow the given requirements:

• The integer consists of the concatenation of three elements from digits in any arbitrary order.
• The integer does not have leading zeros.
• The integer is even.

For example, if the given digits were [1, 2, 3], integers 132 and 312 follow the requirements.

Return a sorted array of the unique integers.

Example 1:

Input: digits = [2,1,3,0]
Output: [102,120,130,132,210,230,302,310,312,320]
Explanation: All the possible integers that follow the requirements are in the output array. 
Notice that there are no odd integers or integers with leading zeros.

Example 2:

Input: digits = [2,2,8,8,2]
Output: [222,228,282,288,822,828,882]
Explanation: The same digit can be used as many times as it appears in digits. 
In this example, the digit 8 is used twice each time in 288, 828, and 882. 

Example 3:

Input: digits = [3,7,5]
Output: []
Explanation: No even integers can be formed using the given digits.

Constraints:

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

Solution

class Solution {
public:
  vector<int> findEvenNumbers(vector<int>& digits) {
    vector<int> count(10);
    for(auto d : digits) {
      count[d] += 1;
    }
    vector<int> answer;
    // with more digit better use recursion
    for(int last = 0; last < 10; last += 2) {
      if(!count[last]) continue;
      count[last] -= 1;
      for(int mid = 0; mid < 10; ++mid) {
        if(!count[mid]) continue;
        count[mid] -= 1;
        for(int front = 1; front < 10; ++ front) {
          if(!count[front]) continue;
          answer.push_back(front * 100 + mid * 10 + last);
        }
        count[mid] += 1;
      }
      count[last] += 1;
    }
    sort(answer.begin(), answer.end());
    return answer;
  }
};

// Accepted
// 79/79 cases passed (0 ms)
// Your runtime beats 100 % of cpp submissions
// Your memory usage beats 87.12 % of cpp submissions (12.5 MB)

or recursion way to solve it

class Solution {
  void getEvenNumber(
    vector<int> &digits,
    vector<int> &answer,
    int restLen,
    int current = 0,
    bool isFirst = true
  ) {
    if(!restLen) {
      answer.push_back(current);
      return;
    }
    int step = 1;
    int start = 0;
    if(restLen == 1) step += 1;
    if(isFirst && restLen != 1) start = 1;
    for(int d = start; d < 10; d += step) {
      if(!digits[d]) continue;
      digits[d] -= 1;
      getEvenNumber(digits, answer, restLen - 1, current * 10 + d, false);
      digits[d] += 1;
    }
  }
public:
  vector<int> findEvenNumbers(vector<int>& digits) {
    vector<int> count(10);
    for(auto d : digits) {
      count[d] += 1;
    }
    vector<int> answer;
    getEvenNumber(count, answer, 3);
    sort(answer.begin(), answer.end());
    return answer;
  }
};

// Accepted
// 79/79 cases passed (0 ms)
// Your runtime beats 100 % of cpp submissions
// Your memory usage beats 87.12 % of cpp submissions (12.5 MB)