1.
Introduction
2.
Problem Statement
3.
Approach
3.1.
Code in C++
3.2.
Complexity Analysis
4.
4.1.
How is an unordered_set implemented in C++?
4.2.
What is the difference between an unordered set and a set?
4.3.
Are there more Data Structures and Algorithms problems in Coding Ninjas Studio?
5.
Conclusion
5.1.
Recommended Problems
Last Updated: Mar 27, 2024
Medium

# Count the Total Numbers With No Repeated Digits in a Range

Gaurish Anand
1 upvote

## Introduction

Before beginning with this question, let's recap what a prefix array is:

Prefix Array is an important technique that helps minimize the repeated calculations in an array and eventually reduces the time complexity.

Example: Let’s define a prefix sum array for the array: [3,4,1,6,2]

prefixSumArray[i] = sum of elements till ith index

prefixSumArray = [3, 3+4, 3+4+1, 3+4+1+6, 3+4+1+6+2]

prefixSumArray = [3, 7, 8 , 14 , 16]

(Also see Data Structures)

## Problem Statement

Count the total numbers with no repeated digits in a range for Q queries.

Example:

1. For L=4 and R=15, the output will be 11 because the numbers with no repeated digits between them are 4, 5, 6, 7, 8, 9, 10, 12, 13, 14, 15

.2. Similarly, For L=1 and R=100, the output will be 90, and for L=5 and R=100, the output will be 86. The numbers between 5 and 100  having repeated digits are 11, 22, 33, 99,100 etc. and with no repeated digits are 5,6,...,17,98 etc.

Also see, Euclid GCD Algorithm

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

}``````

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

### 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.

Live masterclass