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

April LeetCoding Challenge 12

Description

Find the Count of Good Integers

You are given two positive integers n and k.

An integer x is called k-palindromic if:

• x is a palindrome.
• x is divisible by k.

An integer is called good if its digits can be rearranged to form a k-palindromic integer. For example, for k = 2, 2020 can be rearranged to form the k-palindromic integer 2002, whereas 1010 cannot be rearranged to form a k-palindromic integer.

Return the count of good integers containing n digits.

Note that any integer must not have leading zeros, neither before nor after rearrangement. For example, 1010 cannot be rearranged to form 101.

Example 1:

Example 2:

Example 3:

Constraints:

• 1 <= n <= 10
• 1 <= k <= 9

Solution

class Solution {
  static vector<long long> factorial;
public:
  long long countGoodIntegers(int n, int k) {
    unordered_set<string> st;

    int base = pow(10, (n - 1) / 2);
    bool odd = n & 1;
    for(int i = base; i < base * 10; ++i) {
      string s = to_string(i);
      s += string(s.rbegin() + odd, s.rend());
      long long result = stoll(s);

      if(result % k == 0) {
        sort(s.begin(), s.end());
        st.insert(s);
      }
    }

    long long answer = 0;
    for(const auto &s : st) {
      vector<int> count(10);
      for(auto c : s) {
        count[c - '0'] += 1;
      }
      long long total = (n - count[0]) * factorial[n - 1];
      for(auto c : count) {
        total /= factorial[c];
      }
      answer += total;
    }

    return answer;
  }
};

vector<long long> Solution::factorial = [](){
  vector<long long> result(11, 1);
  for(int i = 1; i < 11; ++i) {
    result[i] = result[i - 1] * i;
  }
  return result;
}();