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