Find the Count of Good Integers - Practice Coding Problems

Find the Count of Good Integers - Problem

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: Any integer must not have leading zeros, neither before nor after rearrangement. For example, 1010 cannot be rearranged to form 101.

Input & Output

Example 1 — Basic Case

$ Input: n = 3, k = 5

› Output: 27

💡 Note: For 3-digit numbers, we need palindromes like ABA where A∈{1-9}, B∈{0-9}. Count arrangements that form palindromes divisible by 5.

Example 2 — Single Digit

$ Input: n = 1, k = 4

› Output: 2

💡 Note: Single digits divisible by 4: only 4 and 8. So count is 2.

Example 3 — Even Length

$ Input: n = 2, k = 6

› Output: 4

💡 Note: 2-digit palindromes divisible by 6: must be divisible by both 2 and 3. Examples: 66 (rearrangement of 66).

Constraints

1 ≤ n ≤ 15
1 ≤ k ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input

n=3 digits, k=5 (divisibility requirement)

Process

Find digit arrangements that form palindromes divisible by 5

Output

Count of good integers

Key Takeaway

🎯 Key Insight: Generate palindrome digit patterns and use combinatorics to count valid arrangements without explicit enumeration

Asked in

G Google 15 M Microsoft 12

This problem requires combinatorial enumeration to count digit arrangements that can form k-palindromic numbers. The key insight is to generate palindrome patterns and use mathematical formulas rather than checking all permutations. Best approach uses mathematical formulas with palindrome structure analysis. Time: O(10^(n/2)), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Check All Numbers	O(10^n × n!)	O(n)	Generate all n-digit numbers and check if any permutation forms k-palindromic number
Mathematical Formula Approach	O(10^(n/2))	O(1)	Use number theory and combinatorial formulas to directly calculate the count
Combinatorial Enumeration	O(10^n)	O(n)	Generate palindrome digit patterns and count valid arrangements using combinatorics

Brute Force - Check All Numbers — Algorithm Steps

Generate all n-digit numbers
For each number, generate all digit permutations
Check if any permutation is palindrome and divisible by k

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Numbers

Create all n-digit numbers

Check Permutations

For each number, try all digit arrangements

Verify

Check if any arrangement is palindrome and divisible by k

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>

long long solution(int n, int k) {
    if (n == 1) {
        long long count = 0;
        for (int i = 1; i <= 9; i++) {
            if (i % k == 0) count++;
        }
        return count;
    }
    
    // Simplified approach for demonstration
    return 0; // Placeholder
}

int main() {
    int n, k;
    scanf("%d", &n);
    scanf("%d", &k);
    printf("%lld\n", solution(n, k));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(10^n × n!)

10^n numbers, each with n! permutations to check

⚠ Quadratic Growth

Space Complexity

O(n)

Space to store current number and generate permutations

⚡ Linearithmic Space

12.5K Views

Medium Frequency

~45 min Avg. Time

280 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Check All Numbers — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler