Dado un número entero N , la tarea es contar los números menores o iguales a N de modo que cada número contenga al menos un dígito repetido.
Ejemplos:
Entrada: N = 20
Salida: 1
Explicación:
Los números que contienen al menos un dígito repetido y menores o iguales que N(= 20) son {11}.
Por lo tanto, la salida requerida es 1.Entrada: N = 100
Salida: 10
Explicación:
Los números que contienen al menos un dígito repetido y menores o iguales a N(= 100) son {11, 22, 33, 44, 55, 66, 77, 88, 99, 100} .
Por lo tanto, la salida requerida es 10.
Enfoque: siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos X , para almacenar el recuento total de dígitos en N.
- Inicialice una variable, digamos cntNumbers , para almacenar el recuento total de números menores o iguales a N que consisten en dígitos únicos.
- Calcule el recuento total de números de X dígitos que contienen dígitos únicos y actualice cntNumbers . A continuación se muestra la fórmula para calcular el recuento total de números de X dígitos con todos los dígitos únicos.
Recuento total de números de X dígitos con todos los dígitos únicos = {(9 * factorial(9)) / factorial(10 – X)}
- Calcule el recuento total de números de X dígitos menores o iguales a N que contienen dígitos únicos al verificar todos los valores posibles en cada dígito posible de un número menor o igual a N y actualice cntNumbers .
- Finalmente, imprima el valor de (N – cntNumbers) .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
long factorial(int n)
{
return (n == 1 || n == 0) ? 1 :
n * factorial(n - 1);
}
// Function to count arrangements to
// select K elements from N elements
long NPR(int n, int k)
{
return factorial(n) / factorial(n - k);
}
// Function to count numbers less than or equal
// to N with at least one repeated digits
int cntNumLessThanEqualNRepeatedDigits(int N)
{
// Stores the value of N
int temp = N;
// Stores count of
// digits in N
int X = 0;
// Store all possible
// digits of N
vector<int> nums;
// Calculate digits in N
while(temp)
{
// Update X
X += 1;
// Insert digits of N
// into nums
nums.push_back(temp % 10);
// Update temp
temp /= 10;
}
reverse(nums.begin(), nums.end());
// Count numbers of (X)-digit
// with no repeated digits
int cntNumbers = 0;
// Calculate count of numbers of less than
// (X)-digit and no repeated digits
for(int i = 1; i < X; i++)
{
// Update cntnumbers
cntNumbers += 9 * (factorial(9) /
factorial(10 - i));
}
// Stores unique digits of
// (X)-digit numbers
unordered_set<int> vis;
// Calculate (X) digits
// numbers with no repeated digits
for(int i = 0; i < nums.size(); i++)
{
// Stores count of unique
// value at i_th digit
int k = 0;
// Stores minimum possible value of
// i_th digit of a number
int Min = 0;
// If current digit is the first
// digit of a number
if (i == 0)
{
// Update Min
Min = 1;
}
else
{
// Update Min
Min = 0;
}
// Stores maximum possible value of
// i_th digit if a number
int Max = 0;
// If current digit is the last
// digit of a number
if (i == X - 1)
{
// Update Max
Max = nums[i];
}
else
{
// Update Max
Max = nums[i] - 1;
}
// Iterate over all possible value
// of current digit
for(int j = Min; j <= Max; j++)
{
// If value of current digit
// already occurred in vis
if (vis.find(j) != vis.end())
{
continue;
}
// Update k
k += 1;
}
// Update cntNumbers
cntNumbers += k * (NPR(9 - i,
X - i - 1));
// If current value of i-th digit
// already occurred in vis
if (vis.find(nums[i]) != vis.end())
{
break;
}
// Insert val in vis
vis.insert(nums[i]);
}
// Return total count of numbers less
// than or equal to N with repetition
return (N - cntNumbers);
}
// Driver Code
int main()
{
int N = 100;
cout << cntNumLessThanEqualNRepeatedDigits(N);
return 0;
}
// This code is contributed by Manu Pathria
Java
// Java program to implement
// the above approach
import java.io.*;
import java.util.*;
class GFG{
public static int factorial(int n)
{
return (n == 1 || n == 0) ? 1 :
n * factorial(n - 1);
}
// Function to count arrangements to
// select K elements from N elements
public static int NPR(int n, int k)
{
return factorial(n) / factorial(n - k);
}
// Function to count numbers less than or equal
// to N with at least one repeated digits
public static int cntNumLessThanEqualNRepeatedDigits(int N)
{
// Stores the value of N
int temp = N;
// Stores count of
// digits in N
int X = 0;
// Store all possible
// digits of N
List<Integer> nums = new ArrayList<>();
// Calculate digits in N
while (temp > 0)
{
// Update X
X += 1;
// Insert digits of N
// into nums
nums.add(temp % 10);
// Update temp
temp /= 10;
}
Collections.reverse(nums);
// Count numbers of (X)-digit
// with no repeated digits
int cntNumbers = 0;
// Calculate count of numbers of less than
// (X)-digit and no repeated digits
for(int i = 1; i < X; i++)
{
// Update cntnumbers
cntNumbers += 9 * (factorial(9) /
factorial(10 - i));
}
// Stores unique digits of
// (X)-digit numbers
Set<Integer> vis=new HashSet<>();
// Calculate (X) digits
// numbers with no repeated digits
for(int i = 0; i < nums.size(); i++)
{
// Stores count of unique
// value at i_th digit
int k = 0;
// Stores minimum possible value of
// i_th digit of a number
int Min = 0;
// If current digit is the first
// digit of a number
if (i == 0)
{
// Update Min
Min = 1;
}
else
{
// Update Min
Min = 0;
}
// Stores maximum possible value of
// i_th digit if a number
int Max = 0;
// If current digit is the last
// digit of a number
if (i == X - 1)
{
// Update Max
Max = nums.get(i);
}
else
{
// Update Max
Max = nums.get(i) - 1;
}
// Iterate over all possible value
// of current digit
for(int j = Min; j <= Max; j++)
{
// If value of current digit
// already occurred in vis
if (vis.contains(j))
{
continue;
}
// Update k
k += 1;
}
// Update cntNumbers
cntNumbers += k * (NPR(9 - i,
X - i - 1));
// If current value of i-th digit
// already occurred in vis
if (vis.contains(nums.get(i)))
{
break;
}
// Insert val in vis
vis.add(nums.get(i));
}
// Return total count of numbers less
// than or equal to N with repetition
return (N - cntNumbers);
}
// Driver Code
public static void main(String[] args)
{
int N = 100;
System.out.print(
cntNumLessThanEqualNRepeatedDigits(N));
}
}
// This code is contributed by Manu Pathria
Python3
# Python3 program to implement # the above approach import math # Function to count arrangements to # select K elements from N elements def NPR(n, k): return (math.factorial(n) // math.factorial(n-k)) # Function to count numbers less than or equal # to N with at least one repeated digits def cntNumLessThanEqualNRepeatedDigits(N): # Stores the value of N temp = N # Stores count of # digits in N X = 0; # Store all possible # digits of N nums = [] # Calculate digits in N while(temp): # Update X X += 1 # Insert digits of N # into nums nums.append(temp % 10) # Update temp temp //= 10 # Reverse nums nums.reverse() # Count numbers of (X)-digit # with no repeated digits cntNumbers = 0 # Calculate count of numbers of less than # (X)-digit and no repeated digits for i in range(1, X): # Update cntnumbers cntNumbers += 9 * (math.factorial(9) // math.factorial(10 - i)) # Stores unique digits of # (X)-digit numbers vis = set() # Calculate (X) digits # numbers with no repeated digits for i, val in enumerate(nums): # Stores count of unique # value at i_th digit k = 0 # Stores minimum possible value of # i_th digit of a number Min = 0; # If current digit is the first # digit of a number if i == 0: #Update Min Min = 1 else: # Update Min Min = 0 # Stores maximum possible value of # i_th digit if a number Max = 0; # If current digit is the last # digit of a number if i == X - 1: # Update Max Max = val else: # Update Max Max = val - 1; # Iterate over all possible value # of current digit for j in range(Min, Max + 1): # If value of current digit # already occurred in vis if (j in vis): continue # Update k k += 1 # Update cntNumbers cntNumbers += k * (NPR(9 - i, X - i - 1)) # If current value of i-th digit # already occurred in vis if val in vis: break # Insert val in vis vis.add(val) # Return total count of numbers less # than or equal to N with repetition return (N - cntNumbers) # Driver Code if __name__ == '__main__': N = 100 # Function call print(cntNumLessThanEqualNRepeatedDigits(N))
C#
// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
class GFG {
static int factorial(int n)
{
return (n == 1 || n == 0) ? 1 :
n * factorial(n - 1);
}
// Function to count arrangements to
// select K elements from N elements
static int NPR(int n, int k)
{
return factorial(n) / factorial(n - k);
}
// Function to count numbers less than or equal
// to N with at least one repeated digits
static int cntNumLessThanEqualNRepeatedDigits(int N)
{
// Stores the value of N
int temp = N;
// Stores count of
// digits in N
int X = 0;
// Store all possible
// digits of N
List<int> nums = new List<int>();
// Calculate digits in N
while (temp > 0)
{
// Update X
X += 1;
// Insert digits of N
// into nums
nums.Add(temp % 10);
// Update temp
temp /= 10;
}
nums.Reverse();
// Count numbers of (X)-digit
// with no repeated digits
int cntNumbers = 0;
// Calculate count of numbers of less than
// (X)-digit and no repeated digits
for(int i = 1; i < X; i++)
{
// Update cntnumbers
cntNumbers += 9 * (factorial(9) /
factorial(10 - i));
}
// Stores unique digits of
// (X)-digit numbers
HashSet<int> vis = new HashSet<int>();
// Calculate (X) digits
// numbers with no repeated digits
for(int i = 0; i < nums.Count; i++)
{
// Stores count of unique
// value at i_th digit
int k = 0;
// Stores minimum possible value of
// i_th digit of a number
int Min = 0;
// If current digit is the first
// digit of a number
if (i == 0)
{
// Update Min
Min = 1;
}
else
{
// Update Min
Min = 0;
}
// Stores maximum possible value of
// i_th digit if a number
int Max = 0;
// If current digit is the last
// digit of a number
if (i == X - 1)
{
// Update Max
Max = nums[i];
}
else
{
// Update Max
Max = nums[i] - 1;
}
// Iterate over all possible value
// of current digit
for(int j = Min; j <= Max; j++)
{
// If value of current digit
// already occurred in vis
if (vis.Contains(j))
{
continue;
}
// Update k
k += 1;
}
// Update cntNumbers
cntNumbers += k * (NPR(9 - i,
X - i - 1));
// If current value of i-th digit
// already occurred in vis
if (vis.Contains(nums[i]))
{
break;
}
// Insert val in vis
vis.Add(nums[i]);
}
// Return total count of numbers less
// than or equal to N with repetition
return (N - cntNumbers);
}
static void Main()
{
int N = 100;
Console.WriteLine(cntNumLessThanEqualNRepeatedDigits(N));
}
}
// This code is contributed by divyeshrabadiya07
Javascript
<script>
// Javascript program to implement
// the above approach
function factorial(n)
{
return (n == 1 || n == 0) ? 1 :
n * factorial(n - 1);
}
// Function to count arrangements to
// select K elements from N elements
function NPR(n, k)
{
return factorial(n) / factorial(n - k);
}
// Function to count numbers less than or equal
// to N with at least one repeated digits
function cntNumLessThanEqualNRepeatedDigits(N)
{
// Stores the value of N
var temp = N;
// Stores count of
// digits in N
var X = 0;
// Store all possible
// digits of N
var nums = [];
// Calculate digits in N
while(temp)
{
// Update X
X += 1;
// Insert digits of N
// into nums
nums.push(temp % 10);
// Update temp
temp = parseInt(temp/10);
}
nums.reverse();
// Count numbers of (X)-digit
// with no repeated digits
var cntNumbers = 0;
// Calculate count of numbers of less than
// (X)-digit and no repeated digits
for(var i = 1; i < X; i++)
{
// Update cntnumbers
cntNumbers += 9 * (factorial(9) /
factorial(10 - i));
}
// Stores unique digits of
// (X)-digit numbers
var vis = new Set();
// Calculate (X) digits
// numbers with no repeated digits
for(var i = 0; i < nums.length; i++)
{
// Stores count of unique
// value at i_th digit
var k = 0;
// Stores minimum possible value of
// i_th digit of a number
var Min = 0;
// If current digit is the first
// digit of a number
if (i == 0)
{
// Update Min
Min = 1;
}
else
{
// Update Min
Min = 0;
}
// Stores maximum possible value of
// i_th digit if a number
var Max = 0;
// If current digit is the last
// digit of a number
if (i == X - 1)
{
// Update Max
Max = nums[i];
}
else
{
// Update Max
Max = nums[i] - 1;
}
// Iterate over all possible value
// of current digit
for(var j = Min; j <= Max; j++)
{
// If value of current digit
// already occurred in vis
if (vis.has(j))
{
continue;
}
// Update k
k += 1;
}
// Update cntNumbers
cntNumbers += k * (NPR(9 - i,
X - i - 1));
// If current value of i-th digit
// already occurred in vis
if (vis.has(nums[i]))
{
break;
}
// Insert val in vis
vis.add(nums[i]);
}
// Return total count of numbers less
// than or equal to N with repetition
return (N - cntNumbers);
}
// Driver Code
var N = 100;
document.write( cntNumLessThanEqualNRepeatedDigits(N));
// This code is contributed by rutvik_56.
</script>
Producción:
10
Complejidad de Tiempo: O((log 10 N) 2 )
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por saikumarkudikala y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA