Le nombre total de numéros dans une plage sans doublons

Dans cet article, nous aborderons différentes façons de compter le nombre d'entiers positifs sans répéter les nombres entre une plage donnée de bas à haut. La première méthode est une méthode par force brute qui parcourt tous les nombres de la plage et vérifie s'ils contiennent des nombres en double. Dans la deuxième méthode, nous calculons le nombre requis à l'aide d'un tableau de préfixes et dans la dernière méthode, nous utilisons le concept de mémoire issu de la programmation dynamique pour obtenir le résultat requis.

Énoncé du problème : étant donné deux nombres, de bas en haut, nous devons trouver le nombre de tous les nombres entre bas et haut de telle sorte que le nombre ne contienne aucun chiffre en double.

Méthode 1

Il s'agit de la méthode de la force brute, nous parcourons simplement tous les nombres de bas en haut et vérifions s'ils contiennent des nombres en double. C'est la solution la plus simple à notre problème.

Exemple

La solution de code pour cela est donnée ci-dessous :

#include <bits/stdc++.h>
using namespace std;
// function that checks whether or not the number contains any repeated digits
int count(int number){
	int arr[10] = {0};
	while(number != 0) {
		int digit = number % 10;
		if(arr[digit]>=1)
		{
			return 0;
		}
		arr[digit]++;
		number = number / 10;
	}
	return 1;
}
// this function iterates over all the numbers in the range from low to high and adds the count of numbers having no repeated digits to the result
int numberofnums(int l , int h)
{
	int res = 0;
	for(int iterator = l; iterator < h + 1; ++iterator)
	{
		res = res + count(iterator);
	}

	return res ;
}
int main()
{
	int low = 1, high = 90;
	cout << "The count of numbers with no repeated digits from " << low << " to "<< high << " is "<<numberofnums(low, high);
	return 0;
}

Sortie

The count of numbers with no repeated digits from 1 to 90 is 82

Méthode 2

Dans cette méthode, nous utiliserons un tableau de préfixes pour stocker le nombre d'entiers sans nombres en double jusqu'à l'index "itérateur".

Les étapes impliquées dans cette méthode sont :

• Définissez une fonction pour vérifier si un numéro comporte des chiffres en double.

• Initialisez le tableau de préfixes avec des zéros. Le tableau de préfixes stockera le nombre de chiffres significatifs jusqu'à l'index "itérateur" donné.

• Parcourez chaque nombre de bas en haut, en vérifiant s'il y a des nombres en double. S'il n'y a pas de numéros en double, ajoutez 1 au tableau de préfixes à l'index correspondant.

• Calculez la somme des préfixes du tableau de préfixes. La somme du préfixe vous donnera le nombre total de chiffres significatifs dans la plage.

• Renvoyer la somme du préfixe.

Exemple

Le code de cette approche est donné ci-dessous -

#include <bits/stdc++.h>
using namespace std;
bool isvalid(int number)
{
	int arr[10] = {0};
	while(number != 0)
	{
		int digit = number % 10;
		if(arr[digit]>=1)
		{
			return false;
		}
		arr[digit]++;
		number = number / 10;
	}
	return true;
}

int count(int low, int high) {
    vector<int> prefarray(high+1, 0);
    for (int iterator = low; iterator <= high; iterator++) {
        if (isvalid(iterator)) {
            prefarray[iterator] = 1;
        }
    }
    for (int iterator = 1; iterator <= high; iterator++) {
        prefarray[iterator] += prefarray[iterator-1];
    }
    return prefarray[high] - prefarray[low-1];
}

int main() {
    int low = 21, high = 200;
    int c = count(low, high);
    cout << "The count of numbers with no repeated digits from " << low << " to "<< high << " is "<< c;
    return 0;
}

Sortie

The count of numbers with no repeated digits from 21 to 200 is 143

Complexité temporelle - O(nlogn), où n est (élevé - faible).

Complexité spatiale - O(n)

Méthode 3 Méthode de programmation dynamique

Dans cette approche, nous décomposons le problème en sous-problèmes et stockons les résultats des sous-problèmes dans une table mémoire

Le programme compte le nombre total de chiffres significatifs dans une plage donnée, c'est-à-dire les nombres sans chiffres répétés. Il utilise une approche de programmation dynamique où la fonction dp("iterator",used) renvoie le nombre de chiffres significatifs pouvant être formés à partir de la position "iterator" et dans le nombre "used".

Nous utilisons une table mémorisable pour stocker les résultats de la fonction dp et parcourons la plage de nombres pour appeler la fonction dp pour chaque numéro. La somme des résultats de la fonction dp pour tous les "itérateurs" de départ est le nombre total de chiffres significatifs dans la plage.

Exemple

#include <bits/stdc++.h>
using namespace std;
int dp(int iterator, set<int>& used, unordered_map<string, int>& memo, const string& high_str) {
    if ( memo.count(to_string(iterator) + "|" + to_string(used.size() ))) {
        return memo[to_string(iterator) + "|" + to_string(used.size())];
    }
    if (iterator == high_str.length())
    {
        return 1;
    }
    int count = 0;
    for (int digit = 0; digit < 10; digit++) {
        if (digit == 0 && iterator == 0) {
            continue;
        }
        if (!used.count(digit)) {
            used.insert(digit);
            count += dp(iterator+1, used, memo, high_str);
            used.erase(digit);
        }
    }
    memo[to_string(iterator) + "|" + to_string(used.size())] = count;
    return count;
}

int count_valid_numbers(int low, int high) {
    unordered_map<string, int> memo;
    string high_str = to_string(high);
    int count = 0;
    for (int num = low; num <= high; num++) {
        set<int> used;
        count += dp(0, used, memo, high_str);
    }
    return count;
}

int main() {
    int low = 21, high = 200;
    int count = count_valid_numbers(low, high);
        cout << "The count of numbers with no repeated digits from " << low   <<  " to " << high << " is "<< count;
    return 0;
}

Sortie

The count of numbers with no repeated digits from 21 to 200 is 116640

Conclusion - Dans ce code, nous avons discuté de trois façons de calculer le nombre total de nombres compris entre le plus bas et le plus élevé sans les répéter.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!