Recuento de números palindrómicos de N dígitos divisibles por 9

Dado un número entero N , la tarea es contar la cantidad de números palindrómicos de N dígitos que contienen dígitos del 1 al 9 y son divisibles por 9. 
Ejemplos: 
 

Entrada: N = 1 
Salida: 1 
Explicación: 
Solo 9 es un número de 1 dígito que es palíndromo y divisible por 9.
Entrada: N = 3 
Salida: 9 
Explicación: 
Los números de tres dígitos que son palíndromos y divisibles por 9 son: 
{171, 252 , 333, 414, 585, 666, 747, 828, 999} 
 

Enfoque: la observación clave en el problema es que si el número es divisible por 9, entonces la suma de los dígitos del número también es divisible por 9. Por lo tanto, el problema puede separarse en función de su paridad.
 

• Si N es impar: podemos poner cualquier número del 1 al 9 en la posición 1 a (N-1)/2. De manera similar, los otros dígitos se eligen en orden inverso para formar el número palindrómico y el elemento central se elige para formar el suma de dígitos divisible por 9. Por lo tanto, hay 9 opciones para cada posición de (N-1)/2 dígitos del número por lo que la cuenta de dicho número será: 
   

Count of N-digit Palindromic numbers =
                 9(N-1)/2

• Si N es par: podemos poner cualquier número del 1 al 9 en la posición del 1 al (N-2)/2. De manera similar, los otros dígitos se eligen en orden inverso para formar un número palindrómico y el elemento del medio se elige en forman la suma de dígitos divisible por 9. Por lo tanto, hay 9 opciones para cada posición de (N-2)/2 dígitos del número por lo que la cuenta de dicho número será: 
   

Count of N-digit Palindromic numbers =
                 9(N-2)/2

// C++ implementation to count the
// number of N digit palindromic
// numbers divisible by 9
 
#include <bits/stdc++.h>
 
using namespace std;
 
// Function to find the count of
// N digits palindromic numbers
// which are divisible by 9
int countPalindromic(int n)
{
    int count;
 
    // if N is odd
    if (n % 2 == 1) {
        count = pow(9, (n - 1) / 2);
    }
    // if N is even
    else
    {
        count = pow(9, (n - 2) / 2);
    }
    return count;
}
 
// Driver Code
int main()
{
    int n = 3;
    cout << countPalindromic(n);
    return 0;
}

// Java implementation to count the
// number of N digit palindromic
// numbers divisible by 9
import java.util.*;
 
class GFG{
     
// Function to find the count of
// N digits palindromic numbers
// which are divisible by 9
static int countPalindromic(int n)
{
    int count;
 
    // If N is odd
    if (n % 2 == 1)
    {
        count = (int) Math.pow(9, (n - 1) / 2);
    }
     
    // If N is even
    else
    {
        count = (int) Math.pow(9, (n - 2) / 2);
    }
    return count;
}
 
// Driver Code
public static void main(String[] args)
{
    int n = 3;
    System.out.println(countPalindromic(n));
}
}
 
// This code is contributed by ANKITKUMAR34

# Python3 implementation to count the
# number of N digit palindromic
# numbers divisible by 9
 
# Function to find the count of
# N digits palindromic numbers
# which are divisible by 9
def countPalindromic(n):
     
    count = 0
     
    # If N is odd
    if (n % 2 == 1):
        count = pow(9, (n - 1) // 2)
         
    # If N is even
    else:
        count = pow(9, (n - 2) // 2)
         
    return count
 
# Driver Code
n = 3
print(countPalindromic(n))
 
# This code is contributed by ANKITKUMAR34

// C# implementation to count the
// number of N digit palindromic
// numbers divisible by 9
using System;
class GFG{
     
// Function to find the count of
// N digits palindromic numbers
// which are divisible by 9
static int countPalindromic(int n)
{
    int count;
 
    // If N is odd
    if (n % 2 == 1)
    {
        count = (int) Math.Pow(9, (n - 1) / 2);
    }
     
    // If N is even
    else
    {
        count = (int) Math.Pow(9, (n - 2) / 2);
    }
    return count;
}
 
// Driver Code
public static void Main()
{
    int n = 3;
    Console.Write(countPalindromic(n));
}
}
 
// This code is contributed by Nidhi_biet

<script>
 
// Javascript implementation to count the
// number of N digit palindromic
// numbers divisible by 9
 
// Function to find the count of
// N digits palindromic numbers
// which are divisible by 9
function countPalindromic(n)
{
    var count;
 
    // if N is odd
    if (n % 2 == 1) {
        count = Math.pow(9, (n - 1) / 2);
    }
    // if N is even
    else
    {
        count = Math.pow(9, (n - 2) / 2);
    }
    return count;
}
 
// Driver Code
var n = 3;
document.write( countPalindromic(n));
 
</script>

9

Complejidad de tiempo: O (log ₉ n)

Espacio Auxiliar: O(1)