Recuento de números enteros en un rango dado que consiste solo en un conjunto dado de dígitos

Dados dos enteros L y R , y una array arr[] que contiene enteros de un solo dígito, la tarea es encontrar todos los enteros en el rango [L, R) que consisten en dígitos de una array de dígitos dada. 

Ejemplos:

Entrada: L = 1, R = 100, arr[] = {2, 3, 5, 7}
Salida: 20
Explicación: El número entre 1 y 100 enteros totales que se componen de 2, 3, 5, 7 son:
2, 3, 5, 7, 22, 23, 25, 27, 32, 33, 35, 37, 52, 53, 55, 57, 72, 73, 75 y 77. Total 20.

Entrada: L = 50, R = 60, arr[] = 5
Salida: 1
Explicación: El único número en el rango 50 y 60 55.

Enfoque: La solución al problema se basa en un enfoque codicioso utilizando la siguiente idea:

Recorra cada entero en el rango [L, R) y verifique si consta solo de un conjunto dado de dígitos. 

Siga los pasos a continuación para resolver el problema:

• Iterar sobre el rango [L, R) .
• Comprueba si el número es una combinación de números dados en arr[] o no con la ayuda de un conjunto.
• Si es un subconjunto de dígitos dados, aumente la cuenta en 1; de lo contrario, no.

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

// C++ code to implement the approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function Check number is
// subset of prime digit of not
bool has_val(int x, set<int>& st)
{
    while (x != 0) {
        if (st.find(x % 10) == st.end())
            return false;
        x /= 10;
    }
    return true;
}
 
// Function to find
// non-prime between range
int total_Num(int A, int B, int arr[], int N)
{
    int ans = 0;
    set<int> st;
    for(int i = 0; i < N; i++)
        st.insert(arr[i]);
   
    // Loop to check if number contains
    // only the digits in given set
    for (int k = A; k < B; k++) {
        if (has_val(k, st))
            ans += 1;
    }
    return ans;
}
 
// Driver Code
int main()
{
    int L = 1, R = 100;
    int arr[] = { 2, 3, 5, 7 };
    int N = sizeof(arr) / sizeof(arr[0]);
   
    int ans = total_Num(L, R, arr, N);
    cout << ans;
    return 0;
}

// Java code to implement the approach
import java.util.*;
public class GFG {
 
  // Function Check number is
  // subset of prime digit of not
  static boolean has_val(int x, HashSet<Integer> st)
  {
    while (x != 0) {
      if (st.contains(x % 10) == false)
        return false;
      x /= 10;
    }
    return true;
  }
 
  // Function to find
  // non-prime between range
  static int total_Num(int A, int B, int arr[], int N)
  {
    int ans = 0;
    HashSet<Integer> st = new HashSet<>();
    for (int i = 0; i < N; i++)
      st.add(arr[i]);
 
    // Loop to check if number contains
    // only the digits in given set
    for (int k = A; k < B; k++) {
      if (has_val(k, st))
        ans += 1;
    }
    return ans;
  }
 
  // Driver Code
  public static void main(String args[])
  {
    int L = 1, R = 100;
    int[] arr = { 2, 3, 5, 7 };
    int N = arr.length;
 
    int ans = total_Num(L, R, arr, N);
    System.out.print(ans);
  }
}
 
// This code is contributed by Samim Hossain Mondal.

# python3 code to implement the approach
 
# Function Check number is
# subset of prime digit of not
def has_val(x, st):
 
    while (x != 0):
        if (not x % 10 in st):
            return False
        x //= 10
 
    return True
 
# Function to find
# non-prime between range
def total_Num(A, B, arr, N):
 
    ans = 0
    st = set()
    for i in range(0, N):
        st.add(arr[i])
 
    # Loop to check if number contains
    # only the digits in given set
    for k in range(A, B):
        if (has_val(k, st)):
            ans += 1
 
    return ans
 
# Driver Code
if __name__ == "__main__":
 
    L, R = 1, 100
    arr = [2, 3, 5, 7]
    N = len(arr)
 
    ans = total_Num(L, R, arr, N)
    print(ans)
 
# This code is contributed by rakeshsahni

// C# code to implement the approach
using System;
using System.Collections.Generic;
 
public class GFG{
 
  // Function Check number is
  // subset of prime digit of not
  static bool has_val(int x, HashSet<int> st)
  {
    while (x != 0) {
      if (st.Contains(x % 10) == false)
        return false;
      x /= 10;
    }
    return true;
  }
 
  // Function to find
  // non-prime between range
  static int total_Num(int A, int B, int[] arr, int N)
  {
    int ans = 0;
    HashSet<int> st = new HashSet<int>();
    for (int i = 0; i < N; i++)
      st.Add(arr[i]);
 
    // Loop to check if number contains
    // only the digits in given set
    for (int k = A; k < B; k++) {
      if (has_val(k, st))
        ans += 1;
    }
    return ans;
  }
 
  // Driver Code
  static public void Main (){
 
    int L = 1, R = 100;
    int[] arr = { 2, 3, 5, 7 };
    int N = arr.Length;
 
    int ans = total_Num(L, R, arr, N);
    Console.Write(ans);
  }
}
 
// This code is contributed by hrithikgarg03188.

<script>
       // JavaScript code for the above approach
 
       // Function Check number is
       // subset of prime digit of not
       function has_val(x, st) {
           while (x != 0) {
               if (!st.has(x % 10))
                   return false;
               x = Math.floor(x / 10);
           }
           return true;
       }
 
       // Function to find
       // non-prime between range
       function total_Num(A, B, arr, N) {
           let ans = 0;
           let st = new Set();
           for (let i = 0; i < N; i++)
               st.add(arr[i]);
 
           // Loop to check if number contains
           // only the digits in given set
           for (let k = A; k < B; k++) {
               if (has_val(k, st))
                   ans += 1;
           }
           return ans;
       }
 
       // Driver Code
       let L = 1, R = 100;
       let arr = [2, 3, 5, 7];
       let N = arr.length;
 
       let ans = total_Num(L, R, arr, N);
       document.write(ans);
 
    // This code is contributed by Potta Lokesh
   </script>

20

Complejidad de tiempo: O((RL)*logN)
Espacio auxiliar: O(1)