thảo luận Leetcode mỗi ngày

public class Solution {
    public bool IsValid(string s)
    {
        if (s.Length % 2 != 0)
            return false;
        int left = 0, right = s.Length - 1;
        int sum1 = 0, sum2 = 0;
        while (left < right)
        {
            sum1 += s[left] - '0';
            sum2 += s[right] - '0';
            left++;
            right--;
        }
        return sum1 == sum2;
    }
    public int CountSymmetricIntegers(int low, int high) {
        int result = 0;
        for (int i = low; i <= high; i++)
        {
            if (IsValid(i.ToString()))
                result++;
        }
        return result;
    }
}

/**
 * @param {number} low
 * @param {number} high
 * @return {number}
 */
var countSymmetricIntegers = function(low, high) {
    const isSymmetric = (num) => {
        const arrNum = num.toString()
        if (arrNum.length % 2 != 0) return false
        let left = 0
        let right = 0
        for (let i = 0; i < arrNum.length/2; i++) {
            left+= Number(arrNum[i])
            right+= Number(arrNum[arrNum.length - i - 1])
        }
        return left == right
    }
    let count = 0
    for (let i = low; i <= high; i++)
        if (isSymmetric(i)) count++
    return count
};

class Solution:
    def countSymmetricIntegers(self, low: int, high: int) -> int:
        def isSymmetric(num):
            numStr = str(num)
            if len(numStr) & 1 == 1:
                return False

            count = 0
            runningSum = 0
            while num > 0:
                digit = num%10
                num //= 10
                runningSum += digit if count < len(numStr) // 2 else -digit
                count += 1

            return runningSum == 0

        ans = 0
        for num in range(low, high + 1):
            if isSymmetric(num):
                ans += 1

        return ans

var countGoodIntegers = function (n, k) {
    const s = new Set();
    const F = [1];
    for (let i = 1; i <= n; i++) {
        F[i] = F[i - 1] * i;
    }
    const go = (v, i) => {
        if (i * 2 >= n) {
            if (v % k === 0) {
                s.add(
                    Number(
                        [...String(v)].sort((uu, vv) => vv - uu).join('')
                    )
                );
            }
        } else {
            for (let j = 0; j < 10; j++) {
                if (!i && !j) {
                    continue;
                }
                const u = i === n - i - 1
                    ? j * 10 ** i
                    : j * 10 ** (n - i - 1) + j * 10 ** i;
                go(v + u, i + 1);
            }
        }
    };
    const count = num => {
        let res = F[n];
        const cnt = [];
        while (num > 0) {
            cnt[num % 10] ??= 0;
            cnt[num % 10]++;
            num = Math.trunc(num / 10);
        }
        res -= (cnt[0] ?? 0) * F[n - 1];
        for (let i = 0; i < 10; i++) {
            if (cnt[i] > 0) {
                res /= F[cnt[i]];
            }
        }
        return res;
    };
    go(0, 0);
    return _.sum([...s].map(it => count(it)));
};

class Solution {
  public long countGoodIntegers(int n, int k) {
    long ans = 0;
    long[] factorial = new long[n + 1];
    factorial[1] = 1;
    factorial[0] = 1;
    for (int i = 1; i <= n; i++) {
      factorial[i] = factorial[i - 1] * i;
    }
    int start = (int) Math.pow(10, (n - 2) / 2);

    Set<String> set = new HashSet<>();
    for (int i = start; i < start * 10; i++) {
      if ((n & 1) == 0) {
        String s = String.valueOf(i) + new StringBuilder(String.valueOf(i)).reverse().toString();
        long num = Long.parseLong(s);
        if (num % k == 0) {
          char[] c_array = s.toCharArray();
          Arrays.sort(c_array);
          set.add(new String(c_array));
        }
      } else if (n == 1) {
        if (i % k == 0) {
          set.add(String.valueOf(i));
        }
      } else {//n is odd number greater than 1
        for (char j = '0'; j <= '9'; j++) {
          String s = String.valueOf(i) + j + new StringBuilder(String.valueOf(i)).reverse().toString();
          long num = Long.parseLong(s);
          if (num % k == 0) {
            char[] c_array = s.toCharArray();
            Arrays.sort(c_array);
            set.add(new String(c_array));
          }
        }
      }
    }

    for (String num : set) {
      long cnt = factorial[n];
      int[] freq = new int[10];
      long leading_zero = 0;
      for (char c : num.toCharArray()) {
        freq[c - '0']++;
      }
      if (freq[0] > 0) {
        leading_zero = factorial[n - 1];
        leading_zero /= factorial[freq[0] - 1];
        for (int i = 1; i < 10; i++) {
          leading_zero /= factorial[freq[i]];
        }
      }
      for (int i = 0; i < 10; i++) {
        cnt /= factorial[freq[i]];
      }
      ans += (cnt - leading_zero);
    }
    return ans;
  }
}

class Solution {
    private static final long[] fact = new long[] { 1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800 };
    Set<String> duplicate = new HashSet<>();
   
    public long countGoodIntegers(int n, int k) {
        long min = (long) Math.pow(10, (n - 1) / 2);
        long max = min * 10 - 1;
        long count = 0;
        for (long i = min; i <= max; i++) {
            long parlin = toParlind(i, n);
            if (parlin % k == 0) {
                count += countRearrange(parlin, n);
            }
        }

        return count;
    }

    private long countRearrange(long num, int n) {
        String s = Long.toString(num);
        int[] count = new int[10];
        for (int i = 0; i < s.length(); i++) {
            count[s.charAt(i) - '0']++;
        }
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < 10; i++) {
            sb.append(i).append(count[i]);
        }
        if (duplicate.contains(sb.toString())) {
            return 0;
        }
        duplicate.add(sb.toString());

        long sub = fact[n];
        for (int i = 0; i < 10; i++) {
            if (count[i] > 1) {
                sub /= fact[count[i]];
            }
        }

        if (count[0] > 0) {
            count[0]--;
            long sub2 = fact[n - 1];
            for (int i = 0; i < 10; i++) {
                if (count[i] > 1) {
                    sub2 /= fact[count[i]];
                }
            }
            sub -= sub2;
        }

        return sub;
    }

    private long toParlind(long num, int n) {
        long temp = num;
        if (n % 2 == 1)
            temp /= 10;
        while (temp > 0) {
            num = num * 10 + temp % 10;
            temp /= 10;
        }
        return num;
    }
}

class Solution:
    def countGoodIntegers(self, n: int, k: int) -> int:
        def generatePalindrome():
            half = n//2
            if n%2 == 1:
                half += 1
            
            palindrome = set()
            for i in range(10**(half - 1), 10**half):
                left = str(i)
                right = left[::-1] if n%2 == 0 else left[-2::-1]
                if int(left + right) % k == 0:
                    palindrome.add("".join(sorted(list(left + right))))

            return palindrome
        
        def countAns(num):
            freq = defaultdict(int)
            n = len(num)
            for i in range(n):
                freq[num[i]] += 1

            total = math.factorial(n)
            for key, value in freq.items():
                total//=factorial(value)

            startWithZeros = 0
            if freq['0'] > 0:
                freq['0'] -= 1
                startWithZeros = factorial(n - 1)
                for key, value in freq.items():
                    startWithZeros//=factorial(value)

            return total - startWithZeros

            
        palindrome = generatePalindrome()
        ans = 0
        for item in palindrome:
            ans += countAns(item)
        return ans

class Solution {
    final public int MOD = 1000000007;
    public int countGoodNumbers(long n) {
      return (int)((powMod(5, (n+1)/2) * powMod(4, n/2)) % MOD);
    }
    public long powMod(long base, long exp) {
        long res = 1;
        base = base % MOD;
        while (exp > 0) {
            if ((exp % 2) == 1) {
                res = (res * base) % MOD;
            }
            base = (base * base) % MOD;
            exp = exp / 2;
        }
        return res;
    }

const m = int64(1e9 + 7)
func powmod(a, b int64) int64 {
    res := int64(1)
    for {
        if b == 0 {
            break
        }
        if b&1 == 1 {
            res = (res * a) % m
        }
        a = (a * a) % m
        b >>= 1
    }
    return res
}
func countGoodNumbers(n int64) int {
    if n%2 == 0 {
        return int(powmod(5, n/2) * powmod(4, n/2) % m)
    } else {
        return int(powmod(5, n/2+1) * powmod(4, n/2) % m)
    }
}

class Solution:
    def countGoodNumbers(self, n: int) -> int:
        MOD = 10**9 + 7
        def calc(x, m):
            if m == 0:
                return 1
            return x ** (m % 2) * calc(x**2 % MOD, m // 2) % MOD
        return 5 ** (n % 2) * calc(20, n // 2) % MOD

class Solution:
    def countGoodNumbers(self, n: int) -> int:
        odd = n//2
        even = n-odd
        def binpow(x,n):
            if n==0:
                return 1
            res = binpow(x,n//2)
            if n%2==1:
                res *= res*x
            else:
                res *=res
            return res%(10**9+7)
        return binpow(4,odd)*binpow(5,even) %(10**9+7)

/**
 * @param {number | string | BigInt} n
 * @return {number}
 */
var countGoodNumbers = function(n) {
    const MOD = BigInt(1e9 + 7)
    const even = Math.ceil(n / 2)
    const odd = n - even   

    const pow = (base, exp) => {
        let result = 1n
        base = BigInt(base)
        exp = BigInt(exp)

        while (exp > 0n) {
            if (exp % 2n === 1n) {
                result = (result * base) % MOD
            }
            base = (base * base) % MOD
            exp = exp / 2n
        }

        return result
    };

    return Number((pow(5, even) * pow(4, odd)) % MOD)
};