Dados dos números enteros L y R , la tarea es encontrar el número de números enteros en el rango [L, R] tal que la frecuencia de cada dígito en el número entero sea par.
Ejemplos:
Entrada: L = 47, R = 999
Salida: 5
Explicación: Los enteros que están en el rango [47, 999] y siguen la condición dada son {55, 66, 77, 88, 99}.Entrada: L = 32, R = 1010
Salida: 9
Explicación: Los enteros que están en el rango [32, 1010] y siguen la condición dada son {33, 44, 55, 66, 77, 88, 99, 1001, 1010} .
Enfoque: el problema anterior se puede resolver con la ayuda de máscara de bits y programación dinámica . A continuación se presentan algunas observaciones que se pueden utilizar para resolver el problema dado:
- Se puede usar una máscara de bits que tiene 10 bits para almacenar la paridad de cada dígito en el rango [0, 9] donde un i -ésimo bit establecido representará la frecuencia del dígito i en el entero como impar.
- Definamos una función countInt(X) para encontrar el recuento de enteros válidos en el rango [1, X] . Por lo tanto, la respuesta para el rango [L, R] se puede calcular como countInt(R) – countInt(L-1) .
Considere una array 4D, digamos dp[][][][] , donde dp[mask][length][smaller][started] , donde mask representa la máscara de bits que denota la paridad de cada dígito de 0 a 9 , length representa el total cuenta de dígitos en el número actual, menor representa si el número actual es más pequeño que el límite superior, es decir, se encuentra en el rango dado y comenzó hará un seguimiento de los números repetidos debido a los ceros iniciales. A continuación se detallan los pasos a seguir:
- Cree una función recursiva para iterar a través de cada índice del entero y llame recursivamente a la función para cada dígito válido en el índice actual del entero.
- Mantenga un registro de los ceros iniciales en la variable iniciada para evitar su repetición en el conteo.
- Si el índice actual es el índice más significativo, los dígitos válidos deben estar en el rango [1, 9]; de lo contrario, pueden estar en el rango [0, 9] .
- El dígito actual es un dígito válido si después de poner el dígito en el índice actual del número entero, se forma el número entero <= Límite superior del rango .
- Memorice el conteo para cada estado y devuelva el valor memorizado si el estado actual ya está calculado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Stores the upper limit of the range
string s;
// Stores the overlapping states
int dp[1024][10][2][2];
// Recursive Function to calculate the
// count of valid integers in the range
// [1, s] using memoization
int calcCnt(int mask, int len,
int smaller, int started)
{
// Base Case
if (len == s.size()) {
// If current integer has even
// count of digits and is not
// repeated
return (mask == 0 && started);
}
// If current state is already
// considered
if (dp[mask][len][smaller][started] != -1)
return dp[mask][len][smaller][started];
// Stores the maximum valid digit at
// the current index
int mx = 9;
if (!smaller) {
mx = s[len] - '0';
}
// Stores the count of valid integers
int ans = 0;
// If the current digit is not the
// most significant digit, i.e, the
// integer is already started
if (started) {
// Iterate through all valid digits
for (int i = 0; i <= mx; i++) {
// Recursive call for ith digit
// at the current index
ans += calcCnt(mask ^ (1 << i), len + 1,
smaller || (i < s[len] - '0'), 1);
}
}
else {
// Recursive call for integers having
// leading zeroes in the beginning
ans = calcCnt(mask, len + 1, 1, 0);
// Iterate through all valid digits as
// most significant digits
for (int i = 1; i <= mx; i++) {
// Recursive call for ith digit
// at the current index
ans += calcCnt(mask ^ (1 << i), len + 1,
smaller || (i < s[len] - '0'), 1);
}
}
// Return answer
return dp[mask][len][smaller][started] = ans;
}
// Function to calculate valid number in
// the range [1, X]
int countInt(int x)
{
// Initialize dp array with -1
memset(dp, -1, sizeof(dp));
// Store the range in form of string
s = to_string(x);
// Return Count
return calcCnt(0, 0, 0, 0);
}
// Function to find the count of integers
// in the range [L, R] such that the
// frequency of each digit is even
int countIntInRange(int L, int R)
{
return countInt(R) - countInt(L - 1);
}
// Driver Code
int main()
{
int L = 32, R = 1010;
cout << countIntInRange(L, R);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Stores the upper limit of the range
static String s;
// Stores the overlapping states
static int [][][][] dp = new int[1024][10][2][2];
// Function to convert Integer to boolean
static boolean toBoolean(int smaller)
{
if (smaller >= 1)
return true;
else
return false;
}
// Recursive Function to calculate the
// count of valid integers in the range
// [1, s] using memoization
static int calcCnt(int mask, int len,
int smaller, int started)
{
// Base Case
if (len == s.length()) {
// If current integer has even
// count of digits and is not
// repeated
if (mask == 0 && started !=0)
return 1;
else
return 0;
}
// If current state is already
// considered
if (dp[mask][len][smaller][started] != -1)
return dp[mask][len][smaller][started];
// Stores the maximum valid digit at
// the current index
int mx = 9;
if (smaller == 0) {
mx = (int)s.charAt(len) - 48;
}
// Stores the count of valid integers
int ans = 0;
// If the current digit is not the
// most significant digit, i.e, the
// integer is already started
if (started !=0) {
// Iterate through all valid digits
for (int i = 0; i <= mx; i++) {
// Recursive call for ith digit
// at the current index
ans += calcCnt(mask ^ (1 << i), len + 1,
toBoolean(smaller) || (i < (int)s.charAt(len) - 48)?1:0,
1);
}
}
else {
// Recursive call for integers having
// leading zeroes in the beginning
ans = calcCnt(mask, len + 1, 1, 0);
// Iterate through all valid digits as
// most significant digits
for (int i = 1; i <= mx; i++) {
// Recursive call for ith digit
// at the current index
ans += calcCnt(mask ^ (1 << i), len + 1,
toBoolean(smaller) || (i < (int)s.charAt(len) - 48)?1:0,
1);
}
}
// Return answer
dp[mask][len][smaller][started] = ans;
return ans;
}
// Function to calculate valid number in
// the range [1, X]
static int countInt(int x)
{
// Initialize dp array with -1
for(int i = 0; i < 1024; i++){
for(int j = 0; j < 10; j++){
for(int k = 0; k < 2; k++){
for(int l = 0; l < 2; l++)
dp[i][j][k][l] = -1;
}
}
}
// Store the range in form of string
s = Integer.toString(x);
// Return Count
return calcCnt(0, 0, 0, 0);
}
// Function to find the count of integers
// in the range [L, R] such that the
// frequency of each digit is even
static int countIntInRange(int L, int R)
{
return countInt(R) - countInt(L - 1);
}
// Driver Code
public static void main(String [] args)
{
int L = 32, R = 1010;
System.out.println(countIntInRange(L, R));
}
}
// This code is contributed by ihritik
Python3
# Python program for the above approach
# Stores the upper limit of the range
s = ""
# Stores the overlapping states
dp = [[[[0 for _ in range(2)] for _ in range(2)]
for _ in range(10)] for _ in range(1024)]
# Recursive Function to calculate the
# count of valid integers in the range
# [1, s] using memoization
def calcCnt(mask, sz, smaller, started):
# Base Case
if (sz == len(s)):
# If current integer has even
# count of digits and is not
# repeated
return (mask == 0 and started)
# If current state is already
# considered
if (dp[mask][sz][smaller][started] != -1):
return dp[mask][sz][smaller][started]
# Stores the maximum valid digit at
# the current index
mx = 9
if (not smaller):
mx = ord(s[sz]) - ord('0')
# Stores the count of valid integers
ans = 0
# If the current digit is not the
# most significant digit, i.e, the
# integer is already started
if (started):
# Iterate through all valid digits
for i in range(0, mx+1):
# Recursive call for ith digit
# at the current index
ans += calcCnt(mask ^ (1 << i), sz + 1,
smaller or (i < ord(s[sz]) - ord('0')), 1)
else:
# Recursive call for integers having
# leading zeroes in the beginning
ans = calcCnt(mask, sz + 1, 1, 0)
# Iterate through all valid digits as
# most significant digits
for i in range(1, mx+1):
# Recursive call for ith digit
# at the current index
ans += calcCnt(mask ^ (1 << i), sz + 1,
smaller or (i < ord(s[sz]) - ord('0')), 1)
# Return answer
dp[mask][sz][smaller][started] = ans
return dp[mask][sz][smaller][started]
# Function to calculate valid number in
# the range [1, X]
def countInt(x):
# Initialize dp array with -1
global dp
dp = [[[[-1 for _ in range(2)] for _ in range(2)]
for _ in range(10)] for _ in range(1024)]
# Store the range in form of string
global s
s = str(x)
# Return Count
return calcCnt(0, 0, 0, 0)
# Function to find the count of integers
# in the range [L, R] such that the
# frequency of each digit is even
def countIntInRange(L, R):
return countInt(R) - countInt(L - 1)
# Driver Code
if __name__ == "__main__":
L = 32
R = 1010
print(countIntInRange(L, R))
# This code is contributed by rakeshsahni
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Stores the upper limit of the range
static string s;
// Stores the overlapping states
static int [,,,]dp = new int[1024, 10, 2, 2];
// Recursive Function to calculate the
// count of valid integers in the range
// [1, s] using memoization
static int calcCnt(int mask, int len,
int smaller, int started)
{
// Base Case
if (len == s.Length) {
// If current integer has even
// count of digits and is not
// repeated
if (mask == 0 && started !=0)
return 1;
else
return 0;
}
// If current state is already
// considered
if (dp[mask, len, smaller, started] != -1)
return dp[mask, len, smaller, started];
// Stores the maximum valid digit at
// the current index
int mx = 9;
if (smaller == 0) {
mx = (int)s[len] - 48;
}
// Stores the count of valid integers
int ans = 0;
// If the current digit is not the
// most significant digit, i.e, the
// integer is already started
if (started !=0) {
// Iterate through all valid digits
for (int i = 0; i <= mx; i++) {
// Recursive call for ith digit
// at the current index
ans += calcCnt(mask ^ (1 << i), len + 1,
Convert.ToBoolean(smaller) || (i < (int)s[len] - 48)?1:0,
1);
}
}
else {
// Recursive call for integers having
// leading zeroes in the beginning
ans = calcCnt(mask, len + 1, 1, 0);
// Iterate through all valid digits as
// most significant digits
for (int i = 1; i <= mx; i++) {
// Recursive call for ith digit
// at the current index
ans += calcCnt(mask ^ (1 << i), len + 1,
Convert.ToBoolean(smaller) || (i < (int)s[len] - 48)?1:0,
1);
}
}
// Return answer
dp[mask, len, smaller, started] = ans;
return ans;
}
// Function to calculate valid number in
// the range [1, X]
static int countInt(int x)
{
// Initialize dp array with -1
for(int i = 0; i < 1024; i++){
for(int j = 0; j < 10; j++){
for(int k = 0; k < 2; k++){
for(int l = 0; l < 2; l++)
dp[i, j, k, l] = -1;
}
}
}
// Store the range in form of string
s = x.ToString();
// Return Count
return calcCnt(0, 0, 0, 0);
}
// Function to find the count of integers
// in the range [L, R] such that the
// frequency of each digit is even
static int countIntInRange(int L, int R)
{
return countInt(R) - countInt(L - 1);
}
// Driver Code
public static void Main()
{
int L = 32, R = 1010;
Console.Write(countIntInRange(L, R));
}
}
// This code is contributed by ipg2016107.
Javascript
// Javascript code to implement the approach
// Stores the upper limit of the range
var s = ""
// Stores the overlapping states
var dp = new Array(1024)
// Function to convert Integer to boolean
function toBoolean(smaller)
{
if (smaller >= 1){
return true
}
return false
}
// Recursive Function to calculate the
// count of valid integers in the range
// [1, s] using memoization
function calcCnt(mask, len, smaller, started)
{
// Base Case
if (len == s.length) {
// If current integer has even
// count of digits and is not
// repeated
if (mask == 0 && started !=0)
return 1;
else
return 0;
}
// If current state is already
// considered
if (dp[mask][len][smaller][started] != -1)
return dp[mask][len][smaller][started]
// Stores the maximum valid digit at
// the current index
var mx = 9
if (smaller == 0) {
mx = s.charCodeAt(len) - 48
}
// Stores the count of valid integers
var ans = 0;
// If the current digit is not the
// most significant digit, i.e, the
// integer is already started
if (started !=0) {
// Iterate through all valid digits
for (let i = 0 ; i <= mx ; i++) {
// Recursive call for ith digit
// at the current index
ans += calcCnt(mask ^ (1 << i), len + 1, toBoolean(smaller) || (i < s.charCodeAt(len) - 48) ? 1 : 0, 1)
}
}
else {
// Recursive call for integers having
// leading zeroes in the beginning
ans = calcCnt(mask, len + 1, 1, 0)
// Iterate through all valid digits as
// most significant digits
for (let i = 1 ; i <= mx ; i++) {
// Recursive call for ith digit
// at the current index
ans += calcCnt(mask ^ (1 << i), len + 1, toBoolean(smaller) || (i < s.charCodeAt(len) - 48) ? 1 : 0, 1)
}
}
// Return answer
dp[mask][len][smaller][started] = ans;
return ans;
}
// Function to calculate valid number in
// the range [1, X]
function countInt(x){
// Initialize dp array with -1
for(let i = 0 ; i < 1024 ; i++){
for(let j = 0 ; j < 10 ; j++){
for(let k = 0 ; k < 2 ; k++){
for(let l = 0 ; l < 2 ; l++){
dp[i][j][k][l] = -1;
}
}
}
}
// Store the range in form of string
s = x.toString()
// Return Count
return calcCnt(0, 0, 0, 0)
}
// Function to find the count of integers
// in the range [L, R] such that the
// frequency of each digit is even
function countIntInRange(L, R)
{
return countInt(R) - countInt(L - 1);
}
// Driver Code
var L = 32
var R = 1010
for(let i = 0 ; i < 1024 ; i++){
dp[i] = new Array(10)
for(let j = 0 ; j < 10 ; j++){
dp[i][j] = new Array(2)
for(let k = 0 ; k < 2 ; k++){
dp[i][j][k] = new Array(2)
}
}
}
console.log(countIntInRange(L, R))
// This code is contributed by subhamgoyal2014.
Producción:
9
Tiempo Complejidad: 
Espacio Auxiliar: 
Publicación traducida automáticamente
Artículo escrito por kartikmodi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA