Find the Count of Good Integers solution and explanation

def is_palindrome(x):
    s = str(x)
    return s == s[::-1]

def count_good_integers(n, k):
    count = 0
    start, end = 10**(n-1), 10**n
    for i in range(start, end):
        if i % k == 0 and is_palindrome(i):
            count += 1
    return count

n, k = 3, 5
print(count_good_integers(n, k))

public class Solution {
    public static boolean isPalindrome(int num) {
        String str = Integer.toString(num);
        int len = str.length();
        for(int i = 0; i < len / 2; i++) {
            if(str.charAt(i) != str.charAt(len - i - 1)) {
                return false;
            }
        }
        return true;
    }

    public static int countGoodIntegers(int n, int k) {
        int count = 0;
        int start = (int) Math.pow(10, n - 1);
        int end = (int) Math.pow(10, n);
        for(int i = start; i < end; i++) {
            if(i % k == 0 && isPalindrome(i)) {
                count++;
            }
        }
        return count;
    }

    public static void main(String[] args) {
        int n = 3, k = 5;
        System.out.println(countGoodIntegers(n, k));
    }
}

#include <iostream>
#include <string>
#include <cmath>

bool isPalindrome(int x) {
	std::string s = std::to_string(x);
	int n = s.size();
	for(int i = 0; i < n/2; ++i) {
		if(s[i] != s[n-i-1]) return false;
	}
	return true;
}

int countGoodIntegers(int n, int k) {
	int start = std::pow(10, n-1);
	int end = std::pow(10, n);
	int count = 0;

	for(int i = start; i < end; ++i) {
		if(i % k == 0) {
			if(isPalindrome(i)) count++;
		}
	}

	return count;
}

int main() {
	int n = 3, k = 5;
	std::cout << countGoodIntegers(n, k) << std::endl;
	return 0;
}

function isPalindrome(x) {
    let s = x.toString();
    return s === s.split('').reverse().join('');
}

function countGoodIntegers(n, k) {
    let count = 0;
    let start = Math.pow(10, n - 1);
    let end = Math.pow(10, n);
    for (let i = start; i < end; i++) {
        if (i % k === 0 && isPalindrome(i)) {
            count++;
        }
    }
    return count;
}

let n = 3, k = 5;
console.log(countGoodIntegers(n, k));

#include <stdio.h>
#include <stdbool.h>

bool isPalindrome(int number) {
	char str[12];
	sprintf(str, "%d", number);
	int len = strlen(str);
	for (int i = 0; i < len / 2; i++) {
		if (str[i] != str[len - i - 1])
			return false;
	}
	return true;
}

int countGoodIntegers(int digits, int k) {
	int count = 0;
	int start = pow(10, digits - 1);
	int end = pow(10, digits);
	for (int i = start; i < end; i++) {
		if (i % k == 0 && isPalindrome(i)) {
			count++;
		}
	}
	return count;
}

int main() {
	int n = 3, k = 5;
	int result = countGoodIntegers(n, k);
	printf("%d\n", result);
	return 0;
}

using System;

class Solution {
    public static bool IsPalindrome(int x) {
        string s = x.ToString();
        int len = s.Length;
        for(int i = 0; i < len / 2; ++i) {
            if(s[i] != s[len - i - 1])
                return false;
        }
        return true;
    }

    public static int CountGoodIntegers(int n, int k) {
        int count = 0;
        int start = (int)Math.Pow(10, n - 1);
        int end = (int)Math.Pow(10, n);
        for(int i = start; i < end; ++i) {
            if(i % k == 0 && IsPalindrome(i)) {
                count++;
            }
        }
        return count;
    }

    static void Main() {
        int n = 3, k = 5;
        Console.WriteLine(CountGoodIntegers(n, k));
    }
}

def count_good_integers_dp(n, k):
    # Placeholder for the DP approach implementation
    # Manage DP table for storing calculations
    return 0

n, k = 3, 5
print(count_good_integers_dp(n, k))

// Placeholder for Java implementation of DP based solution
import java.util.*;

public class Solution {
    public static int countGoodIntegersDP(int n, int k) {
        // Current logic placeholder
        return 0;
    }

    public static void main(String[] args) {
        int n = 3, k = 5;
        System.out.println("Number of good integers: " + countGoodIntegersDP(n, k));
    }
}

// C++ implementation for DP approach employing table-based sub-solution retention
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

int countGoodIntegersDP(int n, int k) {
    // Placeholder: Real implementation could involve DP table allocation
    // Insert DP logic for solving sub-problems
    return 0;
}

int main() {
    int n = 3, k = 5;
    cout << "Number of good integers: " << countGoodIntegersDP(n, k) << endl;
    return 0;
}

function countGoodIntegersDP(n, k) {
    // Presume implementation follows an effective DP structure
    return 0;
}

console.log(countGoodIntegersDP(3, 5));

// C language implementation details for DP would follow C programming procedures
// Specifically tailored algorithms for digit combinations might need to maintain state and results
#include <stdio.h>
#include <stdbool.h>
#include <math.h>

int countGoodIntegersDP(int n, int k);

int main() {
    int n = 3, k = 5;
    printf("Number of good integers: %d\n", countGoodIntegersDP(n, k));
    return 0;
}

int countGoodIntegersDP(int n, int k) {
    // Implement detailed DP strategy with state tracking
    return 0; // placeholder, DP logic to be implemented
}

using System;

class Solution {
    public static int CountGoodIntegersDP(int n, int k) {
        // Implement DP strategies for managing repeated calculations
        return 0;
    }

    static void Main() {
        int n = 3, k = 5;
        Console.WriteLine(CountGoodIntegersDP(n, k));
    }
}

function countGoodIntegers(n: number, k: number): number {
    const fac = factorial(n);
    let ans = 0;
    const vis = new Set<string>();
    const base = Math.pow(10, Math.floor((n - 1) / 2));

    for (let i = base; i < base * 10; i++) {
        let s = `${i}`;
        const rev = reverseString(s);
        if (n % 2 === 1) {
            s += rev.substring(1);
        } else {
            s += rev;
        }

        if (+s % k !== 0) {
            continue;
        }

        const bs = Array.from(s).sort();
        const t = bs.join('');

        if (vis.has(t)) {
            continue;
        }

        vis.add(t);

        const cnt = Array(10).fill(0);
        for (const c of t) {
            cnt[+c]++;
        }

        let res = (n - cnt[0]) * fac[n - 1];
        for (const x of cnt) {
            res /= fac[x];
        }
        ans += res;
    }

    return ans;
}

function factorial(n: number): number[] {
    const fac = Array(n + 1).fill(1);
    for (let i = 1; i <= n; i++) {
        fac[i] = fac[i - 1] * i;
    }
    return fac;
}

function reverseString(s: string): string {
    return s.split('').reverse().join('');
}

func factorial(n int) []int64 {
	fac := make([]int64, n+1)
	fac[0] = 1
	for i := 1; i <= n; i++ {
		fac[i] = fac[i-1] * int64(i)
	}
	return fac
}

func countGoodIntegers(n int, k int) (ans int64) {
	fac := factorial(n)
	vis := make(map[string]bool)
	base := int(math.Pow(10, float64((n-1)/2)))

	for i := base; i < base*10; i++ {
		s := strconv.Itoa(i)
		rev := reverseString(s)
		s += rev[n%2:]
		num, _ := strconv.ParseInt(s, 10, 64)
		if num%int64(k) != 0 {
			continue
		}
		bs := []byte(s)
		slices.Sort(bs)
		t := string(bs)

		if vis[t] {
			continue
		}
		vis[t] = true
		cnt := make([]int, 10)
		for _, c := range t {
			cnt[c-'0']++
		}
		res := (int64(n) - int64(cnt[0])) * fac[n-1]
		for _, x := range cnt {
			res /= fac[x]
		}
		ans += res
	}

	return
}

func reverseString(s string) string {
	t := []byte(s)
	for i, j := 0, len(t)-1; i < j; i, j = i+1, j-1 {
		t[i], t[j] = t[j], t[i]
	}
	return string(t)
}

impl Solution {
    pub fn count_good_integers(n: i32, k: i32) -> i64 {
        use std::collections::HashSet;
        let n = n as usize;
        let k = k as i64;
        let mut fac = vec![1_i64; n + 1];
        for i in 1..=n {
            fac[i] = fac[i - 1] * i as i64;
        }

        let mut ans = 0;
        let mut vis = HashSet::new();
        let base = 10_i64.pow(((n - 1) / 2) as u32);

        for i in base..base * 10 {
            let s = i.to_string();
            let rev: String = s.chars().rev().collect();
            let full_s = if n % 2 == 0 {
                format!("{}{}", s, rev)
            } else {
                format!("{}{}", s, &rev[1..])
            };

            let num: i64 = full_s.parse().unwrap();
            if num % k != 0 {
                continue;
            }

            let mut arr: Vec<char> = full_s.chars().collect();
            arr.sort_unstable();
            let t: String = arr.iter().collect();
            if vis.contains(&t) {
                continue;
            }
            vis.insert(t);

            let mut cnt = vec![0; 10];
            for c in arr {
                cnt[c as usize - '0' as usize] += 1;
            }

            let mut res = (n - cnt[0]) as i64 * fac[n - 1];
            for &x in &cnt {
                if x > 0 {
                    res /= fac[x];
                }
            }
            ans += res;
        }

        ans
    }
}