BIWEEKLY CONTEST 138 (Q3)
3272. Find the Count of Good Integers
Leetcode problem : https://leetcode.com/problems/find-th...
Leetcode English Editorial : https://leetcode.com/problems/find-th...

Statement:
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:

Input: n = 3, k = 5

Output: 27

Explanation:

Some of the good integers are:

551 because it can be rearranged to form 515.
525 because it is already k-palindromic.
Example 2:

Input: n = 1, k = 4

Output: 2

Explanation:

The two good integers are 4 and 8.

Example 3:

Input: n = 5, k = 6

Output: 2468



Intuition
Instead of considering each number with n digits and check if they are good numbers, let's take the problem upside down and denombrate the number of permutations (i.e. good numbers) that we can get from the k-palindromes composed of n digits.
This way, we are exhaustive and non-redundant, if we make sure that we don't have duplicate collection.Counters of our k-palindromes =)

Generation of palindromes of size n
So for the first step (i.e. generation of palindromes of size n), we can use the classic trick of concatenating half of the palindrome with its mirrored self.
If it is even, this exact process works
If it is odd, we have to generate the concatenation plus a middle in the middle, the middle being something between 0 and 9.
For instance, for "123321", it is nothing but "123" + "321", "321" being s[::-1] of "123.

Removing duplicates
One issue I faced is that two k-palindromes can have the same set of digits, and thus when I go through my palindromes_filtered list, I do not want to count the permutations (i.e. good numbers) twice.
To avoid this, I used this line :

palindromes_filtered.add(int(''.join(sorted(str(palindrome),reverse=True))))
Which enables me to add to my set only the stringified, sorted versions of my k-palindrome, thus avoiding duplicates counter collections of digits that I then use to denombrate the total number of permutation

Permutations
Now, we only need to denombrate the number of good numbers we can form out of a unique k-palindrome.
This is simple :

permutations = math.factorial(n-1) // math.prod(math.factorial(v) for v in counter.values())
We do need to divide by math.prod(math.factorial(v)) because "111111" has 6! permutations, but all of them are the same. So 6! / 6! = 1, which is the only value I can get out of it.
One trick I used to remove the "0" from those permutations is to fixate the first digit as a character of the string "123456789".

Please subscribe and like
Complexity Analysis
Time Complexity:
The time complexity primarily depends on the number of palindromes generated and the permutations calculated. The generation of palindromes is O(10^(n//2)), and checking each palindrome for divisibility and calculating permutations adds a multiplicative factor.
Space Complexity:
The space complexity is dominated by storing the palindromes, which is also O(10^(n//2)).


#leetcode #biweeklycontest #biweekly138 ~#maths #factorial #factorials #string #array #programming #python #french #competitiveprogramming