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>
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