3272. Find the Count of Good Integers

HardHash TableMathCombinatoricsEnumeration

Problem Description

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.

Intuition

To solve this problem, we need to focus on generating and counting palindromic numbers based on given constraints. The concept revolves around creating half of a palindrome and mirroring it. We can enumerate numbers that can potentially become palindromes by constructing half of the number and then reflecting it.

Start by figuring out possible half-palindromes. For an n-digit palindrome, if n is even, mirror half of the digits; if n is odd, mirror half minus one and adjust for the middle digit.
Check whether each formed number is divisible by k.
Avoid duplicate numbers: Calculate how many different permutations of these digits can be arranged to form the same palindrome, ensuring each unique rearrangement is counted once.
Count palindromes that qualify as k-palindromic by keeping a set to track permutations already processed.
Utilize factorial arithmetic to ascertain the number of valid rearrangements by dividing the factorial of the total digit count by the factorial of repeated digits' counts.

This structured approach efficiently narrows down possibilities by focusing only on valid rearrangements and divisibility, ensuring every eligible k-palindromic number is considered.

Learn more about Math and Combinatorics patterns.

Solution Approach

The solution leverages combinatorial techniques to explore the formation of palindromes. Here's a detailed breakdown:

Pre-computation of Factorials:
Pre-compute the factorial of numbers up to n using a list fac. This allows quick calculation of permutations later.
```
fac = [factorial(i) for i in range(n + 1)]
```

Initialize Variables:
Set up variables for storing results (ans), seen configurations (vis), and the base for half-palinindromes (base).

ans = 0
vis = set()
base = 10 ** ((n - 1) // 2)

Construct Potential Palindromes:
Iterate over numbers forming half the palindrome, then mirror it based on whether n is even or odd.

for i in range(base, base * 10):
    s = str(i)
    s += s[::-1][n % 2 :]

Filter by Divisibility:
Skip numbers that aren't divisible by k.

if int(s) % k:
    continue

Check Unique Permutations:
Sort the digits and check if this combination has already been processed.

t = "".join(sorted(s))
if t in vis:
    continue
vis.add(t)

Count Valid Arrangements:
Calculate the number of unique permutations of digits that form the same palindrome, ensuring no leading zeros by excluding permutations starting with zero.

cnt = Counter(t)
res = (n - cnt["0"]) * fac[n - 1]
for x in cnt.values():
    res //= fac[x]
ans += res

The permutations are computed by dividing the factorial of total digits by the factorial of count of each repeated digit.

Return Result:
Finally, return the accumulated count of valid permutations that give a k-palindromic integer.
```
return ans
```

The algorithm efficiently manages the complexity through factorial arithmetic and a set to handle permutations, ensuring all valid palindromes are precisely counted.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a small example using the provided solution approach. Suppose n = 2 and k = 11. Our goal is to find good integers with 2 digits that can be rearranged into a 2-digit palindromic integer divisible by 11.

Pre-computation of Factorials:
Calculate factorials for numbers up to 2.
fac = [1, 1, 2] (where fac[i] = i!).
Initialize Variables:
Set up the variables:
- ans = 0 for the result count.
- vis = set() to track checked numbers.
- base = 10 ** ((2 - 1) // 2) = 10.
Construct Potential Palindromes:
Iterate over numbers with 1 digit (half of 2), then create their palindrome:
- For i = 1: s = "1" + "1" = "11".
- For i = 2: s = "2" + "2" = "22".
Continue this process up to i = 9.
Filter by Divisibility:
Only keep palindromes divisible by k = 11:
- 11 % 11 == 0, keep 11.
- 22 % 11 == 0, keep 22.
Check Unique Permutations:
For each valid palindrome, ensure its permutation hasn't been checked:
- For 11, rearrange to "11" which is added to vis.
- For 22, rearrange to "22" which is added to vis.
Count Valid Arrangements:
Calculate possible unique permutations:
- For 11: Digits are 1 and 1, total permutations = 2! / (2!) = 1.
- For 22: Digits are 2 and 2, total permutations = 2! / (2!) = 1.
Since leading zeros are not possible with 2 digits, include all valid permutations.
Return Result:
Sum valid counts: ans = 1 + 1 = 2.

The result gives us 2 good integers: 11 and 22.

Solution Implementation

1from math import factorial
2from collections import Counter
3
4class Solution:
5    def countGoodIntegers(self, n: int, k: int) -> int:
6        # Precompute factorials for numbers from 0 to n
7        factorials = [factorial(i) for i in range(n + 1)]
8      
9        total_good_integers = 0
10        visited_patterns = set()
11      
12        # Calculate the starting base number, only considering half of the digits
13        base = 10 ** ((n - 1) // 2)
14      
15        # Iterate over possible combinations for the first half of the digits
16        for i in range(base, base * 10):
17            s = str(i)
18            # Form the palindrome by appending the reverse of the string
19            s += s[::-1][n % 2:]
20          
21            # Check if the number is divisible by k
22            if int(s) % k:
23                continue
24          
25            # Sort and check for uniqueness in the visited set
26            sorted_s = "".join(sorted(s))
27            if sorted_s in visited_patterns:
28                continue
29          
30            visited_patterns.add(sorted_s)
31            count_digits = Counter(sorted_s)
32          
33            # Calculate the number of unique permutations
34            num_permutations = (n - count_digits["0"]) * factorials[n - 1]
35            for cnt in count_digits.values():
36                num_permutations //= factorials[cnt]
37              
38            total_good_integers += num_permutations
39      
40        return total_good_integers
41

1import java.util.*;
2
3class Solution {
4    // Method to count good integers of length n divisible by k
5    public long countGoodIntegers(int n, int k) {
6        // Array to store factorial values
7        long[] factorials = new long[n + 1];
8        factorials[0] = 1;
9        // Calculate factorials from 1 to n
10        for (int i = 1; i <= n; i++) {
11            factorials[i] = factorials[i - 1] * i;
12        }
13
14        long result = 0; // Variable to store the final answer
15        Set<String> visited = new HashSet<>(); // Set to track visited permutations
16        int base = (int) Math.pow(10, (n - 1) / 2); // Base number derived from n
17
18        // Loop through integers starting from base to base * 10
19        for (int i = base; i < base * 10; i++) {
20            String current = String.valueOf(i);
21            StringBuilder reversed = new StringBuilder(current).reverse();
22            // Construct potential number by appending its reverse (considering even/odd n)
23            current += reversed.substring(n % 2);
24          
25            // Check if this number is divisible by k
26            if (Long.parseLong(current) % k != 0) {
27                continue; // Skip if not divisible
28            }
29
30            // Convert current number to a sorted character array
31            char[] digitsArray = current.toCharArray();
32            Arrays.sort(digitsArray);
33            String sortedDigits = new String(digitsArray);
34
35            // Check if this sorted arrangement has been processed before
36            if (visited.contains(sortedDigits)) {
37                continue; // Skip if already visited
38            }
39            visited.add(sortedDigits); // Mark as visited
40
41            // Count occurrences of each digit
42            int[] digitCounts = new int[10];
43            for (char digit : digitsArray) {
44                digitCounts[digit - '0']++;
45            }
46
47            // Calculate permutations of digits with constraints
48            long combinations = (n - digitCounts[0]) * factorials[n - 1];
49            for (int count : digitCounts) {
50                combinations /= factorials[count];
51            }
52            result += combinations; // Add to result
53        }
54
55        return result; // Return the total count of good integers
56    }
57}
58

1class Solution {
2public:
3    long long countGoodIntegers(int n, int k) {
4        // Factorials for all numbers from 0 to n
5        std::vector<long long> factorials(n + 1, 1);
6        for (int i = 1; i <= n; ++i) {
7            factorials[i] = factorials[i - 1] * i; // Calculate factorial iteratively
8        }
9
10        long long result = 0; // Variable to store the final answer
11        std::unordered_set<std::string> visited; // Set to track already considered permutations
12        int baseValue = pow(10, (n - 1) / 2); // Start value for generating palindromes
13
14        // Iterate over potential palindrome starting values
15        for (int i = baseValue; i < baseValue * 10; ++i) {
16            std::string str = std::to_string(i);
17            std::string reversedStr = str;
18            std::reverse(reversedStr.begin(), reversedStr.end());
19            str += reversedStr.substr(n % 2); // Form the complete palindrome
20          
21            if (stoll(str) % k != 0) {
22                continue; // Skip if the palindrome is not divisible by k
23            }
24
25            std::string sortedStr = str;
26            std::sort(sortedStr.begin(), sortedStr.end()); // Sort digits for uniqueness check
27            if (visited.count(sortedStr)) {
28                continue; // Skip if this permutation already counted
29            }
30            visited.insert(sortedStr); // Mark the permutation as visited
31
32            // Count digit frequency
33            std::vector<int> digitCount(10);
34            for (char ch : sortedStr) {
35                digitCount[ch - '0']++;
36            }
37
38            // Calculate the number of unique permutations
39            long long permutations = (n - digitCount[0]) * factorials[n - 1]; // Factorial for unique permutations
40            for (int count : digitCount) {
41                permutations /= factorials[count]; // Divide by factorial of each duplicate digit
42            }
43            result += permutations; // Add permutations count to result
44        }
45        return result; // Return the total number of good integers
46    }
47};
48

1// Calculate factorial numbers from 0 to n and store them in an array.
2function factorial(n: number): number[] {
3    const fac = Array(n + 1).fill(1);
4    // Compute factorial values iteratively.
5    for (let i = 1; i <= n; i++) {
6        fac[i] = fac[i - 1] * i;
7    }
8    return fac;
9}
10
11// Reverse the input string.
12function reverseString(s: string): string {
13    return s.split('').reverse().join('');
14}
15
16// Count the number of good integers of length n divisible by k.
17function countGoodIntegers(n: number, k: number): number {
18    const fac = factorial(n); // Get factorial values.
19    let ans = 0;             // Initialize answer to zero.
20    const vis = new Set<string>(); // Set to track unique permutations.
21    const base = Math.pow(10, Math.floor((n - 1) / 2)); // Calculate base number for integer candidates.
22
23    // Iterate through possible half integer candidates.
24    for (let i = base; i < base * 10; i++) {
25        let s = i.toString(); // Convert number to string.
26        const rev = reverseString(s); // Reverse the string.
27
28        // Create palindromic integer.
29        if (n % 2 === 1) {
30            s += rev.substring(1); // If n is odd, append reversed substring starting from index 1.
31        } else {
32            s += rev; // If n is even, append full reversed string.
33        }
34
35        const num = parseInt(s, 10); // Convert to number.
36        // Skip if not divisible by k.
37        if (num % k !== 0) {
38            continue;
39        }
40
41        // Get sorted digits of the number.
42        const sortedDigits = Array.from(s).sort();
43        const sortedString = sortedDigits.join('');
44
45        // Skip if this permutation has already been counted.
46        if (vis.has(sortedString)) {
47            continue;
48        }
49
50        // Mark this permutation as seen.
51        vis.add(sortedString);
52
53        // Calculate the number of valid permutations.
54        const digitCount = Array(10).fill(0);
55        for (const char of sortedString) {
56            digitCount[+char]++;
57        }
58
59        // Calculate result contribution from this number.
60        let res = (n - digitCount[0]) * fac[n - 1]; // Adjust for leading zeros.
61        for (const count of digitCount) {
62            res /= fac[count]; // Adjust for repeated digits.
63        }
64
65        ans += res; // Add to the answer.
66    }
67
68    return ans; // Return the total count of good integers.
69}
70

Time and Space Complexity

The time complexity of the given code is influenced mainly by the loop iterating from base to base * 10, where base = 10 ** ((n - 1) // 2). This loop iterates 9 * base times. Within each iteration, operations such as string manipulation, sorting, and checking membership in a set add additional overhead. In the worst case, the time complexity is approximately O(9 * 10^{(n-1)//2} * n \log n), primarily dictated by sorting a string of length n.

The space complexity is determined by several factors: storing factorials of numbers up to n, the set vis to keep track of unique sorted strings, and a counter for string characters. The space for storing factorials is O(n), and the space for vis and Counter depends on the number of unique permutations and characters, which is generally O(10^n) in the worst case for the permutations. Thus, the space complexity can be considered approximately O(10^n) in the worst case.

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

You are given an array of intervals where intervals[i] = [start_i, end_i] represent the start and end of the ith interval. You need to merge all overlapping intervals and return an array of the non-overlapping intervals that cover all the intervals in the input.

Sort the intervals by their start time, then iterate through the sorted intervals, merging any overlapping intervals.

Brute force through all interval combinations and find the answer with the least total intervals.

Iterate through the intervals in their original order, merging any overlapping intervals.

Use a priority queue to keep track of the intervals, merging any overlapping intervals.

I don’t know