Recuento de números en el rango [L, R] que satisfacen las condiciones dadas

Dado un rango [L, R] , la tarea es encontrar el conteo de números de este rango que satisfagan las siguientes condiciones: 
 

  1. Todos los dígitos del número son distintos.
  2. Todos los dígitos son menores o iguales a 5.

Ejemplos: 
 

Entrada: L = 4, R = 13 
Salida:
4, 5, 10, 12 y 13 son los únicos 
números válidos en el rango [4, 13].
Entrada: L = 100, R = 1000 
Salida: 100 
 

Enfoque: la pregunta parece simple si el rango es pequeño porque, en ese caso, todos los números del rango se pueden iterar y verificar si son válidos o no. Pero dado que el rango podría ser grande, se puede observar que todos los dígitos de un número válido deben ser distintos y del rango [0, 5], lo que sugiere que el número máximo no puede exceder 543210.
Ahora, en lugar de verificar cada número, el siguiente número válido de la serie se puede generar a partir de los números generados anteriormente. La idea es similar al enfoque discutido aquí .
A continuación se muestra la implementación del enfoque anterior: 
 

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Maximum possible valid number
#define MAX 543210
 
// To store all the required number
// from the range [1, MAX]
vector<string> ans;
 
// Function that returns true if x
// satisfies the given conditions
bool isValidNum(string x)
{
 
    // To store the digits of x
    map<int, int> mp;
 
    for (int i = 0; i < x.length(); i++) {
 
        // If current digit appears more than once
        if (mp.find(x[i] - '0') != mp.end()) {
            return false;
        }
 
        // If current digit is greater than 5
        else if (x[i] - '0' > 5) {
            return false;
        }
 
        // Put the digit in the map
        else {
            mp[x[i] - '0'] = 1;
        }
    }
    return true;
}
 
// Function to generate all the required
// numbers in the range [1, MAX]
void generate()
{
 
    // Insert first 5 valid numbers
    queue<string> q;
    q.push("1");
    q.push("2");
    q.push("3");
    q.push("4");
    q.push("5");
 
    bool flag = true;
 
    // Inserting 0 externally because 0 cannot
    // be the leading digit in any number
    ans.push_back("0");
 
    while (!q.empty()) {
        string x = q.front();
        q.pop();
 
        // If x satisfies the given conditions
        if (isValidNum(x)) {
            ans.push_back(x);
        }
 
        // Cannot append anymore digit as
        // adding a digit will repeat one of
        // the already present digits
        if (x.length() == 6)
            continue;
 
        // Append all the valid digits one by
        // one and push the new generated
        // number to the queue
        for (int i = 0; i <= 5; i++) {
            string z = to_string(i);
 
            // Append the digit
            string temp = x + z;
 
            // Push the newly generated
            // number to the queue
            q.push(temp);
        }
    }
}
 
// Function to compare two strings
// which represent a numerical value
bool comp(string a, string b)
{
    if (a.size() == b.size())
        return a < b;
    else
        return a.size() < b.size();
}
 
// Function to return the count of
// valid numbers in the range [l, r]
int findcount(string l, string r)
{
 
    // Generate all the valid numbers
    // in the range [1, MAX]
    generate();
 
    // To store the count of numbers
    // in the range [l, r]
    int count = 0;
 
    // For every valid number in
    // the range [1, MAX]
    for (int i = 0; i < ans.size(); i++) {
 
        string a = ans[i];
 
        // If current number is within
        // the required range
        if (comp(l, a) && comp(a, r)) {
            count++;
        }
 
        // If number is equal to either l or r
        else if (a == l || a == r) {
            count++;
        }
    }
 
    return count;
}
 
// Driver code
int main()
{
 
    string l = "1", r = "1000";
 
    cout << findcount(l, r);
 
    return 0;
}

Java

// Java implementation of the approach
import java.util.*;
 
class GFG
{
 
// Maximum possible valid number
static int MAX = 543210;
 
// To store all the required number
// from the range [1, MAX]
static Vector<String> ans = new Vector<String>();
 
// Function that returns true if x
// satisfies the given conditions
static boolean isValidNum(String x)
{
 
    // To store the digits of x
    HashMap<Integer,
            Integer> mp = new HashMap<Integer,
                                      Integer>();
 
    for (int i = 0; i < x.length(); i++)
    {
 
        // If current digit appears more than once
        if (mp.containsKey(x.charAt(i) - '0'))
        {
            return false;
        }
 
        // If current digit is greater than 5
        else if (x.charAt(i) - '0' > 5)
        {
            return false;
        }
 
        // Put the digit in the map
        else
        {
            mp.put(x.charAt(i) - '0', 1);
        }
    }
    return true;
}
 
// Function to generate all the required
// numbers in the range [1, MAX]
static void generate()
{
 
    // Insert first 5 valid numbers
    Queue<String> q = new LinkedList<String>();
    q.add("1");
    q.add("2");
    q.add("3");
    q.add("4");
    q.add("5");
 
    boolean flag = true;
 
    // Inserting 0 externally because 0 cannot
    // be the leading digit in any number
    ans.add("0");
 
    while (!q.isEmpty())
    {
        String x = q.peek();
        q.remove();
 
        // If x satisfies the given conditions
        if (isValidNum(x))
        {
            ans.add(x);
        }
 
        // Cannot append anymore digit as
        // adding a digit will repeat one of
        // the already present digits
        if (x.length() == 6)
            continue;
 
        // Append all the valid digits one by
        // one and push the new generated
        // number to the queue
        for (int i = 0; i <= 5; i++)
        {
            String z = String.valueOf(i);
 
            // Append the digit
            String temp = x + z;
 
            // Push the newly generated
            // number to the queue
            q.add(temp);
        }
    }
}
 
// Function to compare two Strings
// which represent a numerical value
static boolean comp(String a, String b)
{
    if (a.length()== b.length())
    {
        int i = a.compareTo(b);
     
        return i < 0 ? true : false;
    }
    else
        return a.length() < b.length();
}
 
// Function to return the count of
// valid numbers in the range [l, r]
static int findcount(String l, String r)
{
 
    // Generate all the valid numbers
    // in the range [1, MAX]
    generate();
 
    // To store the count of numbers
    // in the range [l, r]
    int count = 0;
 
    // For every valid number in
    // the range [1, MAX]
    for (int i = 0; i < ans.size(); i++)
    {
 
        String a = ans.get(i);
 
        // If current number is within
        // the required range
        if (comp(l, a) && comp(a, r))
        {
            count++;
        }
 
        // If number is equal to either l or r
        else if (a == l || a == r)
        {
            count++;
        }
    }
    return count;
}
 
// Driver code
public static void main (String[] args)
{
    String l = "1", r = "1000";
 
    System.out.println(findcount(l, r));
}
}
 
// This code is contributed by PrinciRaj1992

Python3

# Python3 implementation of the approach
from collections import deque
 
# Maximum possible valid number
MAX = 543210
 
# To store all the required number
# from the range [1, MAX]
ans = []
 
# Function that returns true if x
# satisfies the given conditions
def isValidNum(x):
 
    # To store the digits of x
    mp = dict()
 
    for i in range(len(x)):
 
        # If current digit appears more than once
        if (ord(x[i]) - ord('0') in mp.keys()):
            return False
 
        # If current digit is greater than 5
        elif (ord(x[i]) - ord('0') > 5):
            return False
 
        # Put the digit in the map
        else:
            mp[ord(x[i]) - ord('0')] = 1
 
    return True
 
# Function to generate all the required
# numbers in the range [1, MAX]
def generate():
 
    # Insert first 5 valid numbers
    q = deque()
    q.append("1")
    q.append("2")
    q.append("3")
    q.append("4")
    q.append("5")
 
    flag = True
 
    # Inserting 0 externally because 0 cannot
    # be the leading digit in any number
    ans.append("0")
 
    while (len(q) > 0):
        x = q.popleft()
 
        # If x satisfies the given conditions
        if (isValidNum(x)):
            ans.append(x)
 
        # Cannot append anymore digit as
        # adding a digit will repeat one of
        # the already present digits
        if (len(x) == 6):
            continue
 
        # Append all the valid digits one by
        # one and append the new generated
        # number to the queue
        for i in range(6):
            z = str(i)
 
            # Append the digit
            temp = x + z
 
            # Push the newly generated
            # number to the queue
            q.append(temp)
 
# Function to compare two strings
# which represent a numerical value
def comp(a, b):
    if (len(a) == len(b)):
        if a < b:
            return True
    else:
        return len(a) < len(b)
 
# Function to return the count of
# valid numbers in the range [l, r]
def findcount(l, r):
 
    # Generate all the valid numbers
    # in the range [1, MAX]
    generate()
 
    # To store the count of numbers
    # in the range [l, r]
    count = 0
 
    # For every valid number in
    # the range [1, MAX]
    for i in range(len(ans)):
 
        a = ans[i]
 
        # If current number is within
        # the required range
        if (comp(l, a) and comp(a, r)):
            count += 1
 
        # If number is equal to either l or r
        elif (a == l or a == r):
            count += 1
 
    return count
 
# Driver code
l = "1"
r = "1000"
 
print(findcount(l, r))
 
# This code is contributed by Mohit Kumar

C#

// C# implementation of the approach
using System;
using System.Collections.Generic;    
     
class GFG
{
 
// Maximum possible valid number
static int MAX = 543210;
 
// To store all the required number
// from the range [1, MAX]
static List<String> ans = new List<String>();
 
// Function that returns true if x
// satisfies the given conditions
static bool isValidNum(String x)
{
 
    // To store the digits of x
    Dictionary<int, int> mp = new Dictionary<int, int>();
 
    for (int i = 0; i < x.Length; i++)
    {
 
        // If current digit appears more than once
        if (mp.ContainsKey(x[i] - '0'))
        {
            return false;
        }
 
        // If current digit is greater than 5
        else if (x[i] - '0' > 5)
        {
            return false;
        }
 
        // Put the digit in the map
        else
        {
            mp.Add(x[i] - '0', 1);
        }
    }
    return true;
}
 
// Function to generate all the required
// numbers in the range [1, MAX]
static void generate()
{
 
    // Insert first 5 valid numbers
    Queue<String> q = new Queue<String>();
    q.Enqueue("1");
    q.Enqueue("2");
    q.Enqueue("3");
    q.Enqueue("4");
    q.Enqueue("5");
 
    bool flag = true;
 
    // Inserting 0 externally because 0 cannot
    // be the leading digit in any number
    ans.Add("0");
 
    while (q.Count!=0)
    {
        String x = q.Peek();
        q.Dequeue();
 
        // If x satisfies the given conditions
        if (isValidNum(x))
        {
            ans.Add(x);
        }
 
        // Cannot append anymore digit as
        // adding a digit will repeat one of
        // the already present digits
        if (x.Length == 6)
            continue;
 
        // Append all the valid digits one by
        // one and push the new generated
        // number to the queue
        for (int i = 0; i <= 5; i++)
        {
            String z = i.ToString();
 
            // Append the digit
            String temp = x + z;
 
            // Push the newly generated
            // number to the queue
            q.Enqueue(temp);
        }
    }
}
 
// Function to compare two Strings
// which represent a numerical value
static bool comp(String a, String b)
{
    if (a.Length == b.Length)
    {
        int i = a.CompareTo(b);
     
        return i < 0 ? true : false;
    }
    else
        return a.Length < b.Length;
}
 
// Function to return the count of
// valid numbers in the range [l, r]
static int findcount(String l, String r)
{
 
    // Generate all the valid numbers
    // in the range [1, MAX]
    generate();
 
    // To store the count of numbers
    // in the range [l, r]
    int count = 0;
 
    // For every valid number in
    // the range [1, MAX]
    for (int i = 0; i < ans.Count; i++)
    {
 
        String a = ans[i];
 
        // If current number is within
        // the required range
        if (comp(l, a) && comp(a, r))
        {
            count++;
        }
 
        // If number is equal to either l or r
        else if (a == l || a == r)
        {
            count++;
        }
    }
    return count;
}
 
// Driver code
public static void Main (String[] args)
{
    String l = "1", r = "1000";
 
    Console.WriteLine(findcount(l, r));
}
}
 
// This code is contributed by Princi Singh

Javascript

<script>
 
// JavaScript implementation of the approach
 
// Maximum possible valid number
let MAX = 543210;
 
// To store all the required number
// from the range [1, MAX]
let ans = [];
 
// Function that returns true if x
// satisfies the given conditions
function isValidNum(x)
{
    // To store the digits of x
    let mp = new Map();
   
    for (let i = 0; i < x.length; i++)
    {
   
        // If current digit appears more than once
        if (mp.has(x[i].charCodeAt(0) - '0'.charCodeAt(0)))
        {
            return false;
        }
   
        // If current digit is greater than 5
        else if (x[i].charCodeAt(0) - '0'.charCodeAt(0) > 5)
        {
            return false;
        }
   
        // Put the digit in the map
        else
        {
            mp.set(x[i].charCodeAt(0) - '0'.charCodeAt(0), 1);
        }
    }
    return true;
}
 
// Function to generate all the required
// numbers in the range [1, MAX]
function generate()
{
    // Insert first 5 valid numbers
    let q = [];
    q.push("1");
    q.push("2");
    q.push("3");
    q.push("4");
    q.push("5");
   
    let flag = true;
   
    // Inserting 0 externally because 0 cannot
    // be the leading digit in any number
    ans.push("0");
   
    while (q.length!=0)
    {
        let x = q.shift();
         
   
        // If x satisfies the given conditions
        if (isValidNum(x))
        {
            ans.push(x);
        }
   
        // Cannot append anymore digit as
        // adding a digit will repeat one of
        // the already present digits
        if (x.length == 6)
            continue;
   
        // Append all the valid digits one by
        // one and push the new generated
        // number to the queue
        for (let i = 0; i <= 5; i++)
        {
            let z = (i).toString();
   
            // Append the digit
            let temp = x + z;
   
            // Push the newly generated
            // number to the queue
            q.push(temp);
        }
    }
}
 
// Function to compare two Strings
// which represent a numerical value
function comp(a,b)
{
    if (a.length== b.length)
    {
         
       
        return a < b ? true : false;
    }
    else
        return a.length < b.length;
}
 
// Function to return the count of
// valid numbers in the range [l, r]
function findcount(l,r)
{
    // Generate all the valid numbers
    // in the range [1, MAX]
    generate();
   
    // To store the count of numbers
    // in the range [l, r]
    let count = 0;
   
    // For every valid number in
    // the range [1, MAX]
    for (let i = 0; i < ans.length; i++)
    {
   
        let a = ans[i];
   
        // If current number is within
        // the required range
        if (comp(l, a) && comp(a, r))
        {
            count++;
        }
   
        // If number is equal to either l or r
        else if (a == l || a == r)
        {
            count++;
        }
    }
    return count;
}
 
// Driver code
let l = "1", r = "1000";
   
document.write(findcount(l, r));
 
 
// This code is contributed by unknown2108
 
</script>
Producción

130

Otro enfoque : 

El siguiente número válido de la serie se puede generar a partir de los números generados previamente y se utiliza la búsqueda binaria en lugar de la búsqueda lineal para reducir la complejidad del tiempo.

Python3

# Python3 implementation of the approach
# for checking if number has all unique digits
 
 
def possible(x):
    # creating dictonary to check if duplicate digit exists
    d = {}
 
    for i in x:
 
        if i not in d:
 
            d[i] = 1
 
        else:
 
            return 0
 
    return 1
 
# to create a list containing all possible no.
# with unique digits
#digits <= 5
 
 
def total(a):
    # initializing i for the first index of list 'a'
    i = 1
 
    # traversing till i is less than length of list 'a'
    while i < len(a):
 
        # considering ith index value of list 'a'
        x = a[i]
 
        i += 1
 
        # Cannot append anymore digit as
        # adding a digit will repeat one of
        # the already present digits
        if len(x) == 6:
 
            continue
        # Append all the valid digits one by
        # one and append the new generated
        for j in range(6):
            # Append the digit
            z = str(j)
            # If combination satisfies the given conditions
            if possible(x+z):
                # Push the newly generated
                a.append(x+z)
 
# function to print the count within range
# using binary search
 
 
def PrintSolution(a, l, r):
    ans1 = ans2 = 0
 
    low = 0
 
    high = len(a)-1
 
    # finding the index for l
    while low <= high:
        mid = (low+high)//2
 
        if int(a[mid]) == l:
 
            ans1 = mid
 
            break
 
        if int(a[mid]) > l:
            ans1 = mid
            high = mid - 1
 
        else:
 
            low = mid + 1
 
    low = 0
 
    high = len(a) - 1
    # finding index for r
    while low <= high:
 
        mid = (low+high)//2
 
        if int(a[mid]) == r:
 
            ans2 = mid
 
            break
 
        if int(a[mid]) < r:
 
            ans2 = mid
 
            low = mid + 1
 
        else:
 
            high = mid - 1
 
    print(ans2-ans1+1)
 
 
# Driver Code
a = ['0', '1', '2', '3', '4', '5']
 
# calling function to calculate
# all possible combination available
total(a)
 
l = 1
r = 1000
 
PrintSolution(a, l, r)
 
# This code is contributed by Anvesh Govind Saxena
Producción

130

Publicación traducida automáticamente

Artículo escrito por md1844 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *