Count the Total Numbers With No Repeated Digits in a Range

Approach

The naive approach is to traverse through each element in the range [L, R]. But since in this time complexity will be O(N) where N=R-L+1, the more efficient approach is to store the total numbers that don't have any repeated digit until every number (similar to prefix array). 

Make a prefix array where: 

prefixArray[i] = Total count of numbers with no repeated digits in the range 0 to i.

If we want to find the total numbers with no repeated digit in the range [L, R], we can find it in O(1) in the following way:

Query(L,R) = prefixArray[R] - prefixArray[L-1].

Code in C++

#include<iostream>
#include<vector>
#include<unordered_set>
using namespace std;

bool isRepeatedDigitNotPresent(int n){
	// this unordered_set will maintain the digits which have been repeated
	unordered_set<int> u_set; 
	while(n!=0){
		int x = n%10;
		if(u_set.count(x)==1){
			return false;
		}
		u_set.insert(x);
		n = n/10;
	}
	return true;
}

int findCount(int L,int R,vector<int>& prefixArray) {
    return prefixArray[R] - prefixArray[L-1];
}

vector<int> findPrefixArray(){
	// We will precompute the total numbers that have no repeated digit 
	// till every number
	int MAXIMUM = 1e5; 
	vector<int> ans;

	// It will maintain the count of the numbers with no repeated digit till that i
	int count = 0; 
	for(int i=0;i<=MAXIMUM;i++){
		if(isRepeatedDigitNotPresent(i)){
			count++;
		}
		ans.push_back(count);
	}
	return ans;
}

int main(){
	vector<int> prefixArray = findPrefixArray();

	vector<vector<int> > queries;
	queries.push_back({10,12});
	queries.push_back({1,100});
	queries.push_back({40,90});
	queries.push_back({25,100});
	
	for(int i=0;i<queries.size();i++){
		cout<<findCount(queries[i][0],queries[i][1],prefixArray)<<endl;
	}
	
}

You can also try this code with Online C++ Compiler

Run Code

Output

2
90
46
68

Complexity Analysis

Time Complexity 

Since for each query, time complexity will be O(1), time complexity = O(Q)  where Q = number of queries and the time complexity for precomputing the values of the prefix array of length MAXIMUM is O(MAXIMUM).

Space Complexity 

Since we are making an extra array to store the prefix array, space complexity is O(MAXIMUM), where MAXIMUM is the prefix array's length.

Must Read Lower Bound in C++, Strong number in c

Frequently Asked Questions

How is an unordered_set implemented in C++?

Unordered_set is implemented using hash tables where keys are hashed into indices of a hash table so that the insertion is always randomized.

What is the difference between an unordered set and a set?

A set contains a sorted list of unique values, whereas an unordered set contains a list of unique values that may or may not be sorted. The time complexity of insertion in a set is O(log N), whereas, in unordered_set, it is O(1).

Are there more Data Structures and Algorithms problems in Coding Ninjas Studio?

Yes, Coding Ninjas Studio is a platform that provides both practice coding questions and commonly asked interview questions. The more we'll practice, the better our chances are of getting into a dream company of ours.

Conclusion

This article taught us how to make a prefix array and optimize the time complexity of multiple queries. 

Recommended Problems

Count Integers

Digit Count In Range

Prefix Suffix Search

Matrix Range Query

Check out some of the amazing Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Basics of C, Basics of Java, etc. along with some Contests and Interview Experiences only on Coding Ninjas Studio. 

Do check out some of the  Online Mock Test Series as well as Popular Interview Problems from Top companies like Amazon, Adobe, Google, etc. on Coding Ninjas Studio.