Cuente todos los números de N dígitos cuyos dígitos sean múltiplos de X

Dados dos números enteros N y X , la tarea es encontrar el conteo de todos los posibles números de N dígitos cuyos dígitos individuales sean múltiplos de X.

Ejemplos:

Entrada: N = 1, X = 3 
Salida:
Explicación: 
Los números de un solo dígito cuyos dígitos son múltiplos de 3 son 0, 3, 6 y 9. 
Entonces la respuesta será 4.
Entrada: N = 2, X = 4 
Salida:
Explicación: 
Los números de dos dígitos cuyos dígitos son múltiplos de 4 son 40, 44, 48, 80, 84, 88. 
Entonces la respuesta será 6.

Enfoque ingenuo: el enfoque más simple es iterar sobre todos los números de N dígitos , es decir, en el rango [10 N – 1 , 10 N – 1] y para cada número, verificar si cada dígito del número es un múltiplo de X o no . Aumente la cuenta de dichos números e imprima la cuenta final.

Complejidad de tiempo: O((10 N – 10 N – 1 )*N) 
Espacio auxiliar: O(1)

Enfoque eficiente: siga los pasos a continuación para resolver el problema:

  1. Cuente los dígitos totales que son múltiplos de X , denotemos como total_Multiples .
  2. ORGANIZANDO todos los dígitos anteriores en diferentes posiciones para formar un número de N dígitos , se puede obtener el conteo requerido.

    Ilustración: 
    Por ejemplo, N = 2, X = 3
    Los múltiplos de 3 son S = { 0, 3, 6, 9 }

    • Para encontrar todos los números de 2 dígitos , ordena todos los múltiplos de X para formar un número de 2 dígitos y cuéntalo.
    • Ordena los números del conjunto S . Tomar 0 para el bit más significativo dará como resultado un número de 1 dígito, por lo que hay 3 formas de organizar la posición más significativa de un número y hay 4 formas de organizar el último dígito de un número cuyos dígitos son múltiplos de 3
      Entonces total de formas = 3*4 = 12 entonces la respuesta será 12.
  3. De la ilustración anterior, si M es el conteo de todos los múltiplos de X , entonces el conteo requerido de números de N dígitos (para N > 1 ) es igual a (M – 1)*M N – 1 .
  4. Para números de un dígito, la respuesta es M.

A continuación se muestra la implementación del enfoque anterior:

C++

// C++ program for the above approach
  
#include <stdio.h>
#define ll long long
  
// Function to calculate x^n
// using binary-exponentiation
ll power(ll x, ll n)
{
    // Stores the resultant power
    ll temp;
  
    if (n == 0)
        return 1;
  
    // Stores the value of x^(n/2)
    temp = power(x, n / 2);
    if (n % 2 == 0)
        return temp * temp;
    else
        return x * temp * temp;
}
  
// Function to count all N-digit numbers
// whose digits are multiples of x
ll count_Total_Numbers(ll n, ll x)
{
    ll total, multiples = 0;
  
    // Count all digits which
    // are multiples of x
    for (int i = 0; i < 10; i++) {
  
        // Check if current number
        // is a multiple of X
        if (i % x == 0)
  
            // Increase count of multiples
            multiples++;
    }
  
    // Check if it's a 1 digit number
    if (n == 1)
        return multiples;
  
    // Count the total numbers
    total = (multiples - 1)
            * power(multiples, n - 1);
  
    // Return the total numbers
    return total;
}
  
// Driver Code
int main()
{
    // Given N and X
    ll N = 1, X = 3;
  
    // Function Call
    printf("%lld ",
           count_Total_Numbers(N, X));
  
    return 0;
}

Java

// Java program for 
// the above approach
class GFG{
  
// Function to calculate x^n
// using binary-exponentiation
static int power(int x, int n)
{
    
  // Stores the resultant power
  int temp;
  
  if (n == 0)
    return 1;
  
  // Stores the value of x^(n/2)
  temp = power(x, n / 2);
  if (n % 2 == 0)
    return temp * temp;
  else
    return x * temp * temp;
}
  
// Function to count aint N-digit 
// numbers whose digits are multiples 
// of x
static int count_Total_Numbers(int n, 
                               int x)
{
  int total, multiples = 0;
  
  // Count aint digits which
  // are multiples of x
  for (int i = 0; i < 10; i++) 
  {
      
    // Check if current number
    // is a multiple of X
    if (i % x == 0)
  
      // Increase count of multiples
      multiples++;
  }
  
  // Check if it's a 1 digit number
  if (n == 1)
    return multiples;
  
  // Count the total numbers
  total = (multiples - 1) * 
           power(multiples, n - 1);
  
  // Return the total numbers
  return total;
}
  
// Driver Code
public static void main(String[] args)
{
  // Given N and X
  int N = 1, X = 3;
  
  // Function Call
  System.out.printf("%d ", 
                    count_Total_Numbers(N, X));
}
}
  
// This code is contributed by 29AjayKumar

Python3

# Python3 program for the above approach
  
# Function to calculate x^n
# using binary-exponentiation
def power(x, n):
      
    # Stores the resultant power
    temp = []
  
    if (n == 0):
        return 1
  
    # Stores the value of x^(n/2)
    temp = power(x, n // 2)
    if (n % 2 == 0):
        return temp * temp
    else:
        return x * temp * temp
  
# Function to count aN-digit numbers
# whose digits are multiples of x
def count_Total_Numbers(n, x):
      
    total, multiples = 0, 0
  
    # Count adigits which
    # are multiples of x
    for i in range(10):
  
        # Check if current number
        # is a multiple of X
        if (i % x == 0):
  
            # Increase count of multiples
            multiples += 1
  
    # Check if it's a 1 digit number
    if (n == 1):
        return multiples
  
    # Count the total numbers
    total = ((multiples - 1) * 
     power(multiples, n - 1))
  
    # Return the total numbers
    return total
  
# Driver Code
if __name__ == '__main__':
      
    # Given N and X
    N = 1
    X = 3
  
    # Function call
    print(count_Total_Numbers(N, X))
  
# This code is contributed by mohit kumar 29

C#

// C# program for the above approach 
using System;
  
class GFG{
  
// Function to calculate x^n
// using binary-exponentiation
static int power(int x, int n)
{
      
    // Stores the resultant power
    int temp;
      
    if (n == 0)
        return 1;
      
    // Stores the value of x^(n/2)
    temp = power(x, n / 2);
      
    if (n % 2 == 0)
        return temp * temp;
    else
        return x * temp * temp;
}
  
// Function to count aint N-digit 
// numbers whose digits are multiples 
// of x
static int count_Total_Numbers(int n, 
                               int x)
{
    int total, multiples = 0;
      
    // Count aint digits which
    // are multiples of x
    for(int i = 0; i < 10; i++) 
    {
          
        // Check if current number
        // is a multiple of X
        if (i % x == 0)
      
        // Increase count of multiples
        multiples++;
    }
      
    // Check if it's a 1 digit number
    if (n == 1)
        return multiples;
      
    // Count the total numbers
    total = (multiples - 1) * 
             power(multiples, n - 1);
      
    // Return the total numbers
    return total;
}
  
// Driver Code
public static void Main()
{
      
    // Given N and X
    int N = 1, X = 3;
      
    // Function call
    Console.Write(count_Total_Numbers(N, X));
}
}
  
// This code is contributed by sanjoy_62

Javascript

<script>
// Javascript program for the above approach
  
// Function to calculate x^n
// using binary-exponentiation
function power(x, n)
{
  
    // Stores the resultant power
    let temp;
  
    if (n == 0)
        return 1;
  
    // Stores the value of x^(n/2)
    temp = power(x, parseInt(n / 2));
    if (n % 2 == 0)
        return temp * temp;
    else
        return x * temp * temp;
}
  
// Function to count all N-digit numbers
// whose digits are multiples of x
function count_Total_Numbers(n, x)
{
    let total, multiples = 0;
  
    // Count all digits which
    // are multiples of x
    for (let i = 0; i < 10; i++)
    {
  
        // Check if current number
        // is a multiple of X
        if (i % x == 0)
  
            // Increase count of multiples
            multiples++;
    }
  
    // Check if it's a 1 digit number
    if (n == 1)
        return multiples;
  
    // Count the total numbers
    total = (multiples - 1)
            * power(multiples, n - 1);
  
    // Return the total numbers
    return total;
}
  
// Driver Code
  
    // Given N and X
    let N = 1, X = 3;
  
    // Function Call
    document.write(
           count_Total_Numbers(N, X));
  
// This code is contributed by subhammahato348.
</script>
Producción: 

4

Complejidad de tiempo: O(Log N) 
Espacio auxiliar: O(1) 

Publicación traducida automáticamente

Artículo escrito por aimformohan y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *