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: 4
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: 6
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:
- Cuente los dígitos totales que son múltiplos de X , denotemos como total_Multiples .
- 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.
- 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 .
- 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