Números enteros del rango que se componen de un solo dígito distinto

Dados dos enteros L y R que representan un rango [L, R] , la tarea es encontrar el recuento de enteros del rango que se componen de un solo dígito distinto.
Ejemplos: 
 

Input : L = 9, R = 11
Output : 2
Only 9 and 11 have single distinct digit

Input : L = 10, R = 50
Output : 4
11, 22, 33 and 44 are the only valid numbers

Enfoque ingenuo: iterar a través de todos los números y verificar si el número se compone de un solo dígito distinto.
A continuación se muestra la implementación del enfoque anterior:
 

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Boolean function to check
// distinct digits of a number
bool checkDistinct(int x)
{
    // Take last digit
    int last = x % 10;
 
    // Check if all other digits
    // are same as last digit
    while (x) {
        if (x % 10 != last)
            return false;
 
        // Remove last digit
        x = x / 10;
    }
 
    return true;
}
 
// Function to return the count of integers that
// are composed of a single distinct digit only
int findCount(int L, int R)
{
    int count = 0;
 
    for (int i = L; i <= R; i++) {
 
        // If i has single distinct digit
        if (checkDistinct(i))
            count += 1;
    }
 
    return count;
}
 
// Driver code
int main()
{
    int L = 10, R = 50;
 
    cout << findCount(L, R);
 
    return 0;
}

Java

//Java implementation of the approach
 
import java.io.*;
 
class GFG {
     
// Boolean function to check
// distinct digits of a number
static boolean checkDistinct(int x)
{
    // Take last digit
    int last = x % 10;
 
    // Check if all other digits
    // are same as last digit
    while (x >0) {
        if (x % 10 != last)
            return false;
 
        // Remove last digit
        x = x / 10;
    }
 
    return true;
}
 
// Function to return the count of integers that
// are composed of a single distinct digit only
static int findCount(int L, int R)
{
    int count = 0;
 
    for (int i = L; i <= R; i++) {
 
        // If i has single distinct digit
        if (checkDistinct(i))
            count += 1;
    }
 
    return count;
}
 
// Driver code
    public static void main (String[] args) {
 
         
        int L = 10, R = 50;
        System.out.println (findCount(L, R));
    }
//This code is contributed by ajit.   
}

Python3

# Python3 implementation of above approach
 
# Boolean function to check
# distinct digits of a number
def checkDistinct(x):
 
    # Take last digit
    last = x % 10
 
    # Check if all other digits
    # are same as last digit
    while (x):
         
        if (x % 10 != last):
            return False
 
        # Remove last digit
        x = x // 10
 
    return True
 
# Function to return the count of
# integers that are composed of a
# single distinct digit only
def findCount(L, R):
 
    count = 0
 
    for i in range(L, R + 1):
 
        # If i has single distinct digit
        if (checkDistinct(i)):
            count += 1
 
    return count
 
# Driver code
L = 10
R = 50
 
print(findCount(L, R))
 
# This code is contributed
# by saurabh_shukla

C#

// C# implementation of the approach
 using System;
  
class GFG {
      
// Boolean function to check
// distinct digits of a number
static Boolean checkDistinct(int x)
{
    // Take last digit
    int last = x % 10;
  
    // Check if all other digits
    // are same as last digit
    while (x >0) {
        if (x % 10 != last)
            return false;
  
        // Remove last digit
        x = x / 10;
    }
  
    return true;
}
  
// Function to return the count of integers that
// are composed of a single distinct digit only
static int findCount(int L, int R)
{
    int count = 0;
  
    for (int i = L; i <= R; i++) {
  
        // If i has single distinct digit
        if (checkDistinct(i))
            count += 1;
    }
  
    return count;
}
  
// Driver code
    static public void Main (String []args) {
  
          
        int L = 10, R = 50;
        Console.WriteLine (findCount(L, R));
    }   
}
//This code is contributed by Arnab Kundu.

PHP

<?php
// PHP implementation of the approach
 
// Boolean function to check distinct
// digits of a number
function checkDistinct($x)
{
    // Take last digit
    $last = $x % 10;
 
    // Check if all other digits
    // are same as last digit
    while ($x)
    {
        if ($x % 10 != $last)
            return false;
 
        // Remove last digit
        $x = floor($x / 10);
    }
 
    return true;
}
 
// Function to return the count of integers that
// are composed of a single distinct digit only
function findCount($L, $R)
{
    $count = 0;
 
    for ($i = $L; $i <= $R; $i++)
    {
 
        // If i has single distinct digit
        if (checkDistinct($i))
            $count += 1;
    }
 
    return $count;
}
 
// Driver code
$L = 10;
$R = 50;
 
echo findCount($L, $R);
 
// This code is contributed by Ryuga
?>

Javascript

<script>
//javascript implementation of the approach   
// Boolean function to check
    // distinct digits of a number
    function checkDistinct(x) {
        // Take last digit
        var last = x % 10;
 
        // Check if all other digits
        // are same as last digit
        while (x > 0) {
            if (x % 10 != last)
                return false;
 
            // Remove last digit
            x = parseInt(x / 10);
        }
 
        return true;
    }
 
    // Function to return the count of integers that
    // are composed of a single distinct digit only
    function findCount(L , R) {
        var count = 0;
 
        for (i = L; i <= R; i++) {
 
            // If i has single distinct digit
            if (checkDistinct(i))
                count += 1;
        }
 
        return count;
    }
 
    // Driver code
     
 
        var L = 10, R = 50;
        document.write(findCount(L, R));
 
// This code contributed by aashish1995
</script>
Producción: 

4

 

Complejidad de tiempo: O((R – L) * log 10 (R – L))

Espacio Auxiliar: O(1)

Enfoque eficiente: 
 

  • Si L es un número de 2 dígitos y R es un número de 5 dígitos, todos los números de 3 y 4 dígitos de la forma 111, 222, …, 999 y 1111, 2222, …, 9999 serán válidos.
  • Por lo tanto, cuenta = cuenta + (9 * (cuentaDígitos(R) – cuentaDígitos(L) – 1)) .
  • Y, para los números que tienen el mismo número de dígitos que L , cuente todos los números válidos ≥ L .
  • De manera similar, para R cuente todos los números ≤ R .
  • Si countDigits(L) = countDigits(R) , cuente los números válidos ≥ L y excluya los elementos válidos ≥ R .
  • Imprime el conteo al final.

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

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the count of digits of a number
int countDigits(int n)
{
    int count = 0;
 
    while (n > 0) {
        count += 1;
        n /= 10;
    }
 
    return count;
}
 
// Function to return a number that contains only
// digit 'd' repeated exactly count times
int getDistinct(int d, int count)
{
    int num = 0;
    count = pow(10, count - 1);
    while (count > 0) {
        num += (count * d);
        count /= 10;
    }
 
    return num;
}
 
// Function to return the count of integers that
// are composed of a single distinct digit only
int findCount(int L, int R)
{
    int count = 0;
 
    // Count of digits in L and R
    int countDigitsL = countDigits(L);
    int countDigitsR = countDigits(R);
 
    // First digits of L and R
    int firstDigitL = (L / pow(10, countDigitsL - 1));
    int firstDigitR = (R / pow(10, countDigitsR - 1));
 
    // If L has lesser number of digits than R
    if (countDigitsL < countDigitsR) {
 
        count += (9 * (countDigitsR - countDigitsL - 1));
 
        // If the number that starts with firstDigitL and has
        // number of digits = countDigitsL is within the range
        // include the number
        if (getDistinct(firstDigitL, countDigitsL) >= L)
            count += (9 - firstDigitL + 1);
 
        // Exclude the number
        else
            count += (9 - firstDigitL);
 
        // If the number that starts with firstDigitR and has
        // number of digits = countDigitsR is within the range
        // include the number
        if (getDistinct(firstDigitR, countDigitsR) <= R)
            count += firstDigitR;
 
        // Exclude the number
        else
            count += (firstDigitR - 1);
    }
 
    // If both L and R have equal number of digits
    else {
 
        // Include the number greater than L upto
        // the maximum number whose digit = coutDigitsL
        if (getDistinct(firstDigitL, countDigitsL) >= L)
            count += (9 - firstDigitL + 1);
        else
            count += (9 - firstDigitL);
 
        // Exclude the numbers which are greater than R
        if (getDistinct(firstDigitR, countDigitsR) <= R)
            count -= (9 - firstDigitR);
        else
            count -= (9 - firstDigitR + 1);
    }
 
    // Return the count
    return count;
}
 
// Driver code
int main()
{
    int L = 10, R = 50;
 
    cout << findCount(L, R);
 
    return 0;
}

Java

// java  implementation of the approach
import java.io.*;
 
class GFG {
    
 
// Function to return the count of digits of a number
static int countDigits(int n)
{
    int count = 0;
 
    while (n > 0) {
        count += 1;
        n /= 10;
    }
 
    return count;
}
 
// Function to return a number that contains only
// digit 'd' repeated exactly count times
static int getDistinct(int d, int count)
{
    int num = 0;
    count = (int)Math.pow(10, count - 1);
    while (count > 0) {
        num += (count * d);
        count /= 10;
    }
 
    return num;
}
 
// Function to return the count of integers that
// are composed of a single distinct digit only
static int findCount(int L, int R)
{
    int count = 0;
 
    // Count of digits in L and R
    int countDigitsL = countDigits(L);
    int countDigitsR = countDigits(R);
 
    // First digits of L and R
    int firstDigitL = (L /(int)Math. pow(10, countDigitsL - 1));
    int firstDigitR = (R / (int)Math.pow(10, countDigitsR - 1));
 
    // If L has lesser number of digits than R
    if (countDigitsL < countDigitsR) {
 
        count += (9 * (countDigitsR - countDigitsL - 1));
 
        // If the number that starts with firstDigitL and has
        // number of digits = countDigitsL is within the range
        // include the number
        if (getDistinct(firstDigitL, countDigitsL) >= L)
            count += (9 - firstDigitL + 1);
 
        // Exclude the number
        else
            count += (9 - firstDigitL);
 
        // If the number that starts with firstDigitR and has
        // number of digits = countDigitsR is within the range
        // include the number
        if (getDistinct(firstDigitR, countDigitsR) <= R)
            count += firstDigitR;
 
        // Exclude the number
        else
            count += (firstDigitR - 1);
    }
 
    // If both L and R have equal number of digits
    else {
 
        // Include the number greater than L upto
        // the maximum number whose digit = coutDigitsL
        if (getDistinct(firstDigitL, countDigitsL) >= L)
            count += (9 - firstDigitL + 1);
        else
            count += (9 - firstDigitL);
 
        // Exclude the numbers which are greater than R
        if (getDistinct(firstDigitR, countDigitsR) <= R)
            count -= (9 - firstDigitR);
        else
            count -= (9 - firstDigitR + 1);
    }
 
    // Return the count
    return count;
}
 
// Driver code
 
 
    public static void main (String[] args) {
        int L = 10, R = 50;
 
    System.out.println( findCount(L, R));
    }
}
// This code is contributed by inder_verma.

Python3

# Python3 implementation of the approach
 
# Function to return the count
# of digits of a number
def countDigits(n):
    count = 0
 
    while (n > 0):
        count += 1
        n //= 10
 
    return count
 
# Function to return a number that contains only
# digit 'd' repeated exactly count times
def getDistinct(d, count):
    num = 0
    count = pow(10, count - 1)
    while (count > 0):
        num += (count * d)
        count //= 10
 
    return num
 
# Function to return the count of integers that
# are composed of a single distinct digit only
def findCount(L, R):
    count = 0
 
    # Count of digits in L and R
    countDigitsL = countDigits(L)
    countDigitsR = countDigits(R)
 
    # First digits of L and R
    firstDigitL = (L // pow(10, countDigitsL - 1))
    firstDigitR = (R // pow(10, countDigitsR - 1))
 
    # If L has lesser number of digits than R
    if (countDigitsL < countDigitsR):
 
        count += (9 * (countDigitsR - countDigitsL - 1))
 
        # If the number that starts with firstDigitL
        # and has number of digits = countDigitsL is
        # within the range include the number
        if (getDistinct(firstDigitL, countDigitsL) >= L):
            count += (9 - firstDigitL + 1)
 
        # Exclude the number
        else:
            count += (9 - firstDigitL)
 
        # If the number that starts with firstDigitR
        # and has number of digits = countDigitsR is
        # within the range include the number
        if (getDistinct(firstDigitR, countDigitsR) <= R):
            count += firstDigitR
 
        # Exclude the number
        else:
            count += (firstDigitR - 1)
 
    # If both L and R have equal number of digits
    else:
 
        # Include the number greater than L upto
        # the maximum number whose digit = coutDigitsL
        if (getDistinct(firstDigitL, countDigitsL) >= L):
            count += (9 - firstDigitL + 1)
        else:
            count += (9 - firstDigitL)
 
        # Exclude the numbers which are greater than R
        if (getDistinct(firstDigitR, countDigitsR) <= R):
            count -= (9 - firstDigitR)
        else:
            count -= (9 - firstDigitR + 1)
 
    # Return the count
    return count
 
# Driver code
L = 10
R = 50
 
print(findCount(L, R))
 
# This code is contributed by Mohit Kumar

C#

// C# implementation of the approach
using System;
 
class GFG
{
 
// Function to return the count
// of digits of a number
static int countDigits(int n)
{
    int count = 0;
 
    while (n > 0)
    {
        count += 1;
        n /= 10;
    }
 
    return count;
}
 
// Function to return a number that contains only
// digit 'd' repeated exactly count times
static int getDistinct(int d, int count)
{
    int num = 0;
    count = (int)Math.Pow(10, count - 1);
    while (count > 0)
    {
        num += (count * d);
        count /= 10;
    }
 
    return num;
}
 
// Function to return the count of integers that
// are composed of a single distinct digit only
static int findCount(int L, int R)
{
    int count = 0;
 
    // Count of digits in L and R
    int countDigitsL = countDigits(L);
    int countDigitsR = countDigits(R);
 
    // First digits of L and R
    int firstDigitL = (L / (int)Math.Pow(10, countDigitsL - 1));
    int firstDigitR = (R / (int)Math.Pow(10, countDigitsR - 1));
 
    // If L has lesser number of digits than R
    if (countDigitsL < countDigitsR)
    {
 
        count += (9 * (countDigitsR - countDigitsL - 1));
 
        // If the number that starts with firstDigitL
        // and has number of digits = countDigitsL is
        // within the range include the number
        if (getDistinct(firstDigitL, countDigitsL) >= L)
            count += (9 - firstDigitL + 1);
 
        // Exclude the number
        else
            count += (9 - firstDigitL);
 
        // If the number that starts with firstDigitR
        // and has number of digits = countDigitsR is
        // within the range include the number
        if (getDistinct(firstDigitR, countDigitsR) <= R)
            count += firstDigitR;
 
        // Exclude the number
        else
            count += (firstDigitR - 1);
    }
 
    // If both L and R have equal number of digits
    else
    {
 
        // Include the number greater than L upto
        // the maximum number whose digit = coutDigitsL
        if (getDistinct(firstDigitL, countDigitsL) >= L)
            count += (9 - firstDigitL + 1);
        else
            count += (9 - firstDigitL);
 
        // Exclude the numbers which are
        // greater than R
        if (getDistinct(firstDigitR, countDigitsR) <= R)
            count -= (9 - firstDigitR);
        else
            count -= (9 - firstDigitR + 1);
    }
 
    // Return the count
    return count;
}
 
// Driver code
public static void Main()
{
    int L = 10, R = 50;
 
    Console.WriteLine(findCount(L, R));
}
}
 
// This code is contributed
// by Akanksha Rai

Javascript

<script>
 
    // Javascript implementation of the approach
     
    // Function to return the count
    // of digits of a number
    function countDigits(n)
    {
        let count = 0;
 
        while (n > 0)
        {
            count += 1;
            n = parseInt(n / 10, 10);
        }
 
        return count;
    }
 
    // Function to return a number that contains only
    // digit 'd' repeated exactly count times
    function getDistinct(d, count)
    {
        let num = 0;
        count = parseInt(Math.pow(10, count - 1), 10);
        while (count > 0)
        {
            num += (count * d);
            count = parseInt(count / 10, 10);
        }
 
        return num;
    }
 
    // Function to return the count of integers that
    // are composed of a single distinct digit only
    function findCount(L, R)
    {
        let count = 0;
 
        // Count of digits in L and R
        let countDigitsL = countDigits(L);
        let countDigitsR = countDigits(R);
 
        // First digits of L and R
        let firstDigitL = parseInt(L / parseInt(Math.pow(10,
        countDigitsL - 1), 10), 10);
        let firstDigitR = parseInt(R / parseInt(Math.pow(10,
        countDigitsR - 1), 10), 10);
 
        // If L has lesser number of digits than R
        if (countDigitsL < countDigitsR)
        {
 
            count += (9 * (countDigitsR - countDigitsL - 1));
 
            // If the number that starts with firstDigitL
            // and has number of digits = countDigitsL is
            // within the range include the number
            if (getDistinct(firstDigitL, countDigitsL) >= L)
                count += (9 - firstDigitL + 1);
 
            // Exclude the number
            else
                count += (9 - firstDigitL);
 
            // If the number that starts with firstDigitR
            // and has number of digits = countDigitsR is
            // within the range include the number
            if (getDistinct(firstDigitR, countDigitsR) <= R)
                count += firstDigitR;
 
            // Exclude the number
            else
                count += (firstDigitR - 1);
        }
 
        // If both L and R have equal number of digits
        else
        {
 
            // Include the number greater than L upto
            // the maximum number whose digit = coutDigitsL
            if (getDistinct(firstDigitL, countDigitsL) >= L)
                count += (9 - firstDigitL + 1);
            else
                count += (9 - firstDigitL);
 
            // Exclude the numbers which are
            // greater than R
            if (getDistinct(firstDigitR, countDigitsR) <= R)
                count -= (9 - firstDigitR);
            else
                count -= (9 - firstDigitR + 1);
        }
 
        // Return the count
        return count;
    }
     
    let L = 10, R = 50;
  
    document.write(findCount(L, R));
     
</script>
Producción: 

4

 

Complejidad de tiempo: O (nlogn)

Espacio Auxiliar: O(1)

Publicación traducida automáticamente

Artículo escrito por saurabh_shukla 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 *