Nos dan dos números enteros n y d, necesitamos contar todos los números de n dígitos que no tienen el dígito d.
Ejemplo :
Input : n = 2, d = 7 Output : 72 All two digit numbers that don't have 7 as digit are 10, 11, 12, 13, 14, 15, 16, 18, ..... Input : n = 3, d = 9 Output : 648
Una solución simple es atravesar todos los números de d dígitos. Para cada número, verifique si tiene x como dígito o no.
Enfoque eficiente En este método, verificamos primero si el dígito excluido d es cero o distinto de cero. Si es cero, tenemos 9 números (del 1 al 9) como primer número; de lo contrario, tenemos 8 números (excluyendo el dígito x y el 0). Luego, para todos los demás dígitos, tenemos 9 opciones, es decir (0 a 9 excluyendo el dígito d). Simplemente llamamos a la función digitNumber con n-1 dígitos como primer número, ya encontramos que puede ser 8 o 9 y simplemente lo multiplicamos. Para otros números, verificamos si los dígitos son impares o incluso si es impar, llamamos a la función digitNumber con (n-1)/2 dígitos y la multiplicamos por 9; de lo contrario, llamamos a la función digitNumber con n/2 dígitos y los almacenamos en resultado y tomamos cuadrado de resultado.
Ilustración :
Number from 1 to 7 excluding digit 9. digits multiple number 1 8 8 2 8*9 72 3 8*9*9 648 4 8*9*9*9 5832 5 8*9*9*9*9 52488 6 8*9*9*9*9*9 472392 7 8*9*9*9*9*9*9 4251528
Como podemos ver, en cada paso somos la mitad del número de dígitos. Supongamos que tenemos 7 dígitos en esto que llamamos función de main con 6 (7-1) dígitos. cuando reducimos la mitad de los dígitos nos quedamos con 3 (6/2) dígitos. Debido a esto, tenemos que multiplicar el resultado de 3 dígitos consigo mismo para obtener el resultado de 6 dígitos. Del mismo modo, para 3 dígitos tenemos dígitos impares, tenemos dígitos impares. Encontramos el resultado con 1 ((3-1)/2) dígitos y encontramos el cuadrado del resultado y lo multiplicamos por 9, porque encontramos el resultado para d-1 dígitos.
C++
// C++ Implementation of above method
#include <bits/stdc++.h>
#define mod 1000000007
using namespace std;
// Finding number of possible number with
// n digits excluding a particular digit
long long digitNumber(long long n) {
// Checking if number of digits is zero
if (n == 0)
return 1;
// Checking if number of digits is one
if (n == 1)
return 9;
// Checking if number of digits is odd
if (n % 2) {
// Calling digitNumber function
// with (digit-1)/2 digits
long long temp = digitNumber((n - 1) / 2) % mod;
return (9 * (temp * temp) % mod) % mod;
} else {
// Calling digitNumber function
// with n/2 digits
long long temp = digitNumber(n / 2) % mod;
return (temp * temp) % mod;
}
}
int countExcluding(int n, int d)
{
// Calling digitNumber function
// Checking if excluding digit is
// zero or non-zero
if (d == 0)
return (9 * digitNumber(n - 1)) % mod;
else
return (8 * digitNumber(n - 1)) % mod;
}
// Driver function to run above program
int main() {
// Initializing variables
long long d = 9;
int n = 3;
cout << countExcluding(n, d) << endl;
return 0;
}
Java
// Java Implementation of above method
import java.lang.*;
class GFG {
static final int mod = 1000000007;
// Finding number of possible number with
// n digits excluding a particular digit
static int digitNumber(long n) {
// Checking if number of digits is zero
if (n == 0)
return 1;
// Checking if number of digits is one
if (n == 1)
return 9;
// Checking if number of digits is odd
if (n % 2 != 0) {
// Calling digitNumber function
// with (digit-1)/2 digits
int temp = digitNumber((n - 1) / 2) % mod;
return (9 * (temp * temp) % mod) % mod;
}
else {
// Calling digitNumber function
// with n/2 digits
int temp = digitNumber(n / 2) % mod;
return (temp * temp) % mod;
}
}
static int countExcluding(int n, int d) {
// Calling digitNumber function
// Checking if excluding digit is
// zero or non-zero
if (d == 0)
return (9 * digitNumber(n - 1)) % mod;
else
return (8 * digitNumber(n - 1)) % mod;
}
// Driver function to run above program
public static void main(String[] args) {
// Initializing variables
int d = 9;
int n = 3;
System.out.println(countExcluding(n, d));
}
}
// This code is contributed by Anant Agarwal.
Python3
# Python Implementation # of above method mod=1000000007 # Finding number of # possible number with # n digits excluding # a particular digit def digitNumber(n): # Checking if number # of digits is zero if (n == 0): return 1 # Checking if number # of digits is one if (n == 1): return 9 # Checking if number # of digits is odd if (n % 2!=0): # Calling digitNumber function # with (digit-1)/2 digits temp = digitNumber((n - 1) // 2) % mod return (9 * (temp * temp) % mod) % mod else: # Calling digitNumber function # with n/2 digits temp = digitNumber(n // 2) % mod return (temp * temp) % mod def countExcluding(n,d): # Calling digitNumber function # Checking if excluding digit is # zero or non-zero if (d == 0): return (9 * digitNumber(n - 1)) % mod else: return (8 * digitNumber(n - 1)) % mod # Driver code d = 9 n = 3 print(countExcluding(n, d)) # This code is contributed # by Anant Agarwal.
C#
// C# Implementation of above method
using System;
class GFG {
static int mod = 1000000007;
// Finding number of possible number with
// n digits excluding a particular digit
static int digitNumber(long n) {
// Checking if number of digits is zero
if (n == 0)
return 1;
// Checking if number of digits is one
if (n == 1)
return 9;
// Checking if number of digits is odd
if (n % 2 != 0) {
// Calling digitNumber function
// with (digit-1)/2 digits
int temp = digitNumber((n - 1) / 2) % mod;
return (9 * (temp * temp) % mod) % mod;
}
else {
// Calling digitNumber function
// with n/2 digits
int temp = digitNumber(n / 2) % mod;
return (temp * temp) % mod;
}
}
static int countExcluding(int n, int d) {
// Calling digitNumber function
// Checking if excluding digit is
// zero or non-zero
if (d == 0)
return (9 * digitNumber(n - 1)) % mod;
else
return (8 * digitNumber(n - 1)) % mod;
}
// Driver function to run above program
public static void Main() {
// Initializing variables
int d = 9;
int n = 3;
Console.WriteLine(countExcluding(n, d));
}
}
// This code is contributed by vt_m.
PHP
<?php
// PHP Implementation
// of above method
$mod = 1000000007;
// Finding number of
// possible number with
// n digits excluding
// a particular digit
function digitNumber($n)
{
global $mod;
// Checking if number
// of digits is zero
if ($n == 0)
return 1;
// Checking if number
// of digits is one
if ($n == 1)
return 9;
// Checking if number
// of digits is odd
if ($n % 2 != 0)
{
// Calling digitNumber
// function with
// (digit-1)/2 digits;
$temp = digitNumber(($n -
1) / 2) % $mod;
return (9 * ($temp * $temp) %
$mod) % $mod;
}
else
{
// Calling digitNumber
// function with n/2 digits
$temp = digitNumber($n /
2) % $mod;
return ($temp *
$temp) % $mod;
}
}
function countExcluding($n, $d)
{
global $mod;
// Calling digitNumber
// function Checking if
// excluding digit is
// zero or non-zero
if ($d == 0)
return (9 * digitNumber($n -
1)) % $mod;
else
return (8 * digitNumber($n -
1)) % $mod;
}
// Driver code
$d = 9;
$n = 3;
print(countExcluding($n, $d));
// This code is contributed by
// Manish Shaw(manishshaw1)
?>
Javascript
<script>
// JavaScript Implementation of above method
const mod = 1000000007;
// Finding number of possible number with
// n digits excluding a particular digit
function digitNumber(n) {
// Checking if number of digits is zero
if (n == 0)
return 1;
// Checking if number of digits is one
if (n == 1)
return 9;
// Checking if number of digits is odd
if (n % 2) {
// Calling digitNumber function
// with (digit-1)/2 digits
let temp = digitNumber((n - 1) / 2) % mod;
return (9 * (temp * temp) % mod) % mod;
} else {
// Calling digitNumber function
// with n/2 digits
let temp = digitNumber(n / 2) % mod;
return (temp * temp) % mod;
}
}
function countExcluding(n, d)
{
// Calling digitNumber function
// Checking if excluding digit is
// zero or non-zero
if (d == 0)
return (9 * digitNumber(n - 1)) % mod;
else
return (8 * digitNumber(n - 1)) % mod;
}
// Driver function to run above program
// Initializing variables
let d = 9;
let n = 3;
document.write(countExcluding(n, d) + "<br>");
// This code is contributed by Surbhi Tyagi.
</script>
648
Complejidad de tiempo: O (log n), donde n representa el número entero dado.
Espacio auxiliar: O (logn), debido al espacio de pila recursivo.
Publicación traducida automáticamente
Artículo escrito por rishabh1322 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA