Dados tres números enteros positivos N , X e Y , la tarea es contar números de N dígitos que contengan X o Y solo como dígitos y la suma de los dígitos también contiene X o Y. Dado que el conteo puede ser muy grande, imprima el módulo de conteo 10 9 + 7 .
Ejemplos:
Entrada: N = 2, X = 1, Y = 2
Salida: 1
Explicación: Todos los números de 2 dígitos posibles que se pueden formar usando X e Y son 11, 12, 21, 22. Entre ellos, solo 11 es un número válido ya que su suma de dígitos es 2 (= Y).Entrada: N = 3, X = 1, Y = 5
Salida: 4
Explicación: Todos los números posibles de 3 dígitos que se pueden formar usando X e Y son 111, 115, 151, 155. Pero solo 155, 515, 551 y 555 satisface la condición dada. Por lo tanto, la cuenta es 4.
Enfoque ingenuo: el enfoque más simple para resolver este problema mediante el uso de la recursividad . En cada paso, hay 2 opciones, colocar el dígito X o Y en la posición actual y calcular la suma de los dígitos cuando la longitud del número formado sea igual a N. Si la suma también está formada solo por X o Y , cuente este número. Después de verificar todos los números, imprima el módulo de conteo 10 9 + 7 .
Complejidad temporal: O(2 N )
Espacio auxiliar: O(1)
Enfoque eficiente: el enfoque anterior se puede optimizar utilizando la programación dinámica , ya que este problema tiene propiedades de subestructura óptima y subproblemas superpuestos . Los cálculos de los mismos subproblemas se pueden evitar usando una array auxiliar dp[N][sum] para almacenar el valor cuando el número de dígitos que quedan es N y la suma de los dígitos completos es la suma . A continuación se muestran los pasos:
- Inicialice una array auxiliar dp[][] para almacenar cálculos intermedios.
- En cada paso, hay 2 opciones para colocar el dígito X o Y en la posición actual.
- Cuando el número de dígitos que quedan es 0 , verifique si la suma de dígitos se puede hacer usando X o Y. En caso afirmativo, incremente el valor del estado actual en 1 .
- De lo contrario, actualice el estado actual como 0 .
- Si se encuentra el mismo subproblema, devuelva el valor ya calculado módulo 10 9 + 7 .
- Coloque el dígito X y el dígito Y en la posición actual y recurra a las posiciones restantes, y pase la suma de los dígitos en cada paso.
- Para cada llamada recursiva del valor x e y, actualice el estado actual como la suma de los valores devueltos por estos estados.
- Después de los pasos anteriores, imprima el valor de dp[N][0] como el conteo resultante.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Stores the value of overlapping
// states
int dp[1000 + 5][9000 + 5];
int mod = 1000000007;
// Function to check whether a number
// have only digits X or Y or not
int check(int sum, int x, int y)
{
// Until sum is positive
while (sum > 0) {
int ln = sum % 10;
// If any digit is not
// X or Y then return 0
if (ln != x && ln != y) {
return 0;
}
sum /= 10;
}
// Return 1
return 1;
}
// Function to find the count of
// numbers that are formed by digits
// X and Y and whose sum of digit
// also have digit X or Y
int countNumbers(int n, int x, int y, int sum)
{
// Initialize dp array
memset(dp, -1, sizeof(dp));
// Base Case
if (n == 0) {
// Check if sum of digits
// formed by only X or Y
return check(sum, x, y);
}
// Return the already computed
if (dp[n][sum] != -1) {
return dp[n][sum] % mod;
}
// Place the digit X at the
// current position
int option1 = countNumbers(n - 1, x,
y, sum + x) % mod;
// Place the digit Y at the
// current position
int option2 = countNumbers(n - 1, x,
y, sum + y) % mod;
// Update current state result
return dp[n][sum] = (option1 + option2) % mod;
}
// Driver Code
int main()
{
int N = 3, X = 1, Y = 5;
// Function Call
cout << countNumbers(N, X, Y, 0) % mod;
// This code is contributed by bolliranadheer
}
Java
// Java program for the above approach
import java.util.*;
public class Main {
// Stores the value of overlapping
// states
static int dp[][] = new int[1000 + 5][9000 + 5];
static int mod = 1000000007;
// Function to find the count of
// numbers that are formed by digits
// X and Y and whose sum of digit
// also have digit X or Y
public static int countNumbers(int n, int x, int y,
int sum)
{
// Initialize dp array
for (int i[] : dp)
Arrays.fill(i, -1);
// Base Case
if (n == 0) {
// Check if sum of digits
// formed by only X or Y
return check(sum, x, y);
}
// Return the already computed
if (dp[n][sum] != -1) {
return dp[n][sum] % mod;
}
// Place the digit X at the
// current position
int option1
= countNumbers(n - 1, x, y, sum + x) % mod;
// Place the digit Y at the
// current position
int option2
= countNumbers(n - 1, x, y, sum + y) % mod;
// Update current state result
return dp[n][sum] = (option1 + option2) % mod;
}
// Function to check whether a number
// have only digits X or Y or not
public static int check(int sum, int x, int y)
{
// Until sum is positive
while (sum > 0) {
int ln = sum % 10;
// If any digit is not
// X or Y then return 0
if (ln != x && ln != y) {
return 0;
}
sum /= 10;
}
// Return 1
return 1;
}
// Driver Code
public static void main(String args[])
{
int N = 3, X = 1, Y = 5;
// Function Call
System.out.println(countNumbers(N, X, Y, 0) % mod);
}
}
Python3
# Python3 program for the above approach # Stores the value of overlapping # states dp = [[-1 for x in range(9000 + 5)] for y in range(1000 + 5)] mod = 1000000007 # Function to check whether a number # have only digits X or Y or not def check(sum, x, y): # Until sum is positive while (sum > 0): ln = sum % 10 # If any digit is not # X or Y then return 0 if (ln != x and ln != y): return 0 sum //= 10 # Return 1 return 1 # Function to find the count of # numbers that are formed by digits # X and Y and whose sum of digit # also have digit X or Y def countNumbers(n, x, y, sum): # Initialize dp array global dp # Base Case if (n == 0): # Check if sum of digits # formed by only X or Y return check(sum, x, y) # Return the already computed if (dp[n][sum] != -1): return dp[n][sum] % mod # Place the digit X at the # current position option1 = countNumbers(n - 1, x, y, sum + x) % mod # Place the digit Y at the # current position option2 = countNumbers(n - 1, x, y, sum + y) % mod # Update current state result dp[n][sum] = (option1 + option2) % mod return dp[n][sum] # Driver Code if __name__ == "__main__": N = 3 X = 1 Y = 5 # Function Call print(countNumbers(N, X, Y, 0) % mod) # This code is contributed by chitranayal
C#
// C# program for the above approach
using System;
class GFG{
// Stores the value of overlapping
// states
static int [,]dp = new int[100 + 5, 900 + 5];
static int mod = 10000007;
// Function to find the count of
// numbers that are formed by digits
// X and Y and whose sum of digit
// also have digit X or Y
public static int countNumbers(int n, int x,
int y, int sum)
{
// Initialize dp array
for(int i = 0; i < dp.GetLength(0); i++)
{
for(int j = 0; j < dp.GetLength(1); j++)
{
dp[i, j] = -1;
}
}
// Base Case
if (n == 0)
{
// Check if sum of digits
// formed by only X or Y
return check(sum, x, y);
}
// Return the already computed
if (dp[n, sum] != -1)
{
return dp[n, sum] % mod;
}
// Place the digit X at the
// current position
int option1 = countNumbers(n - 1, x, y,
sum + x) % mod;
// Place the digit Y at the
// current position
int option2 = countNumbers(n - 1, x, y,
sum + y) % mod;
// Update current state result
return dp[n,sum] = (option1 + option2) % mod;
}
// Function to check whether a number
// have only digits X or Y or not
public static int check(int sum, int x, int y)
{
// Until sum is positive
while (sum > 0)
{
int ln = sum % 10;
// If any digit is not
// X or Y then return 0
if (ln != x && ln != y)
{
return 0;
}
sum /= 10;
}
// Return 1
return 1;
}
// Driver Code
public static void Main(String []args)
{
int N = 3, X = 1, Y = 5;
// Function Call
Console.WriteLine(countNumbers(
N, X, Y, 0) % mod);
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// JavaScript program for the above approach
// Stores the value of overlapping
// states
let dp = [];
for(let i = 0;i<1005;i++){
dp[i] = [];
for(let j = 0;j<9005;j++){
dp[i][j] = 0;
}
}
let mod = 1000000007;
// Function to check whether a number
// have only digits X or Y or not
function check( sum, x, y)
{
// Until sum is positive
while (sum > 0) {
let ln = sum % 10;
// If any digit is not
// X or Y then return 0
if (ln != x && ln != y) {
return 0;
}
sum = Math.floor(sum/10);
}
// Return 1
return 1;
}
// Function to find the count of
// numbers that are formed by digits
// X and Y and whose sum of digit
// also have digit X or Y
function countNumbers(n, x, y, sum)
{
// Initialize dp array
for(let i = 0;i<1005;i++){
for(let j = 0;j<9005;j++){
dp[i][j] = -1;
}
}
// Base Case
if (n == 0) {
// Check if sum of digits
// formed by only X or Y
return check(sum, x, y);
}
// Return the already computed
if (dp[n][sum] != -1) {
return dp[n][sum] % mod;
}
// Place the digit X at the
// current position
let option1 = countNumbers(n - 1, x,
y, sum + x) % mod;
// Place the digit Y at the
// current position
let option2 = countNumbers(n - 1, x,
y, sum + y) % mod;
// Update current state result
return dp[n][sum] = (option1 + option2) % mod;
}
// Driver Code
let N = 3, X = 1, Y = 5;
// Function Call
document.write(countNumbers(N, X, Y, 0) % mod);
</script>
Producción
4
Complejidad de Tiempo: (N*sum)
Espacio Auxiliar: O(N*sum)
Publicación traducida automáticamente
Artículo escrito por hemanthswarna1506 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA