The total number of numbers in a range without duplicates

In this article, we will discuss different ways to count the number of positive integers without repeating numbers between a given range Low to High. The first method is a brute force method which iterates over all numbers in the range and checks if they contain duplicate numbers. In the second method we calculate the required count using prefix array and in the last method we use the memory concept from dynamic programming to obtain the required result.

Problem Statement: Given two numbers, from low to high, we have to find the count of all numbers between low and high such that the number does not contain any repeated digits.

method 1

This is the brute force method, we just iterate through all the numbers from low to high and check if they contain any duplicate numbers. This is the simplest solution to our problem.

Example

The same code solution is given below:

#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;
}

Output

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

Method 2

In this approach we will use a prefix array to store the count of integers without duplicate numbers up to the index "iterator".

The steps involved in this method are:

• Define a function to check if a number has duplicate digits.

• Initialize the prefix array with zeros. The prefix array will store the number of significant digits up to the given index "iterator".

• Traverse each number from low to high, checking if there are duplicate numbers. If there are no duplicate numbers, add 1 to the prefix array at the corresponding index.

• Calculate the prefix sum of the prefix array. The prefix sum will give you the total number of significant digits in the range.

• Return the prefix sum.

Example

The code for this method is given below -

#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;
}

Output

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

Time complexity - O(nlogn), where n is (high - low).

Space complexity - O(n)

Method 3 Dynamic programming method

In this approach, we decompose the problem into sub-problems and store the results of the sub-problems in a memory table

The program counts the total number of significant digits in a given range, i.e. numbers without repeated digits. It uses a dynamic programming approach where the function dp("iterator",used) returns the number of significant digits that can be formed starting from position "iterator" and in the number "used".

We use a memtable to store the results of the dp function and iterate over the range of numbers to call the dp function for each number. The sum of the results of the dp function for all starting "iterators" is the total number of significant digits in the range.

Example

#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;
}

Output

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

Conclusion - In this code, we have discussed three ways to count the total number of numbers in the range from low to high without duplicates.

The above is the detailed content of The total number of numbers in a range without duplicates. For more information, please follow other related articles on the PHP Chinese website!