Total Numbers With no Repeated Digits in a Range

You are given a range of numbers (start, end). The given task says to find out the total numbers of numbers with no repeated digits in a range.

Example

Input:

10 50

Output:

37

Explanation:

10 has no repeated digit. 11 has a repeated digit. 12 has no repeated digit. whereas 22, 33 has a repeated digit. So when we found the numbers that have no repeated digit, we will count that in our result.

Algorithm

1. Declare a Set and a vector.
2. Push the 0 and 1 into the vector and find out all the factors in term of 10, and store the remainders into the set. If the set already contains that number return 0 else return 1.
3. Get that number and add it into the vector.
4. For every query, return the difference of vector[end] and vector[start].

Explanation for Total Numbers With no Repeated Digits in a Range

We have given a range. We have asked to find out the total number of the number that comes in a given range has no repeated digit in the number itself. For this, we are going to use the collection framework. We will be using set and vector. Set is to store the uncommon factors or remainder of a number and vector is to store the number filtered from the set. We know that few of them only a number in any 10s digits place is no repeated, like from 1 to 10, there is no repeating number. From 11 to 10 and 21 to 30, there are two numbers that have repeated digits as 11 and 22, this goes the same.

We will add the number 0 and 1 into the vector, from the value 2 to the given value, whatever it can be. Get the number that has a factor or remainder in terms of 10, as mentioned above. We will get those remainders and add into the set if set already contains that number as a remainder. Return 0 else add that remainder to the set. As it will be a new number or remainder and return 1. Keep traversing till the value becomes 0. Here we will get the number from the like 0 or 1, and add it with the number fetching it through a vector, and push the count to the vector itself.

For each query give, we will be returning the difference of numbers at the right position, which means the right range, and the numbers at the left position means the number at the left range in the vector. We will return this difference, this we will be the required answer.

Implementation

C++ program for Total Numbers With no Repeated Digits in a Range

#include <iostream>
#include<vector>
#include<unordered_set>

using namespace std;

int MAX = 1000;

vector<int> numbers = {0};

int getRepeatedNumber(int n)
{

    unordered_set<int> SET;
    int rem;

    while (n != 0)
    {
        rem = n % 10;
        if (SET.find(rem) != SET.end())
            return 0;

        SET.insert(rem);
        n = n / 10;
    }
    return 1;
}

void buildSetOfNumbers(int MAX)
{

    numbers.push_back(getRepeatedNumber(1));

    for (int i = 2; i < MAX + 1; i++)
        numbers.push_back(getRepeatedNumber(i) + numbers[i-1]);
}

int getNumber(int left,int right)
{
    return numbers[right] - numbers[left-1];
}
int main()
{
    int Left = 10, Right = 50;
    buildSetOfNumbers(MAX);

    cout << getNumber(Left, Right) << endl;

    return 0;
}

37

Java program for Total Numbers With no Repeated Digits in a Range

import java.util.Vector;
import java.util.HashSet;

class repeatedDigits
{
    private static int MAX = 100;
    private static Vector<Integer> numbers = new Vector<>();
    
    static int getRepeatedNumber(int n)
    {
        HashSet<Integer> set = new HashSet<>();
        int rem;

        while (n != 0)
        {
            rem = n % 10;

            if (set.contains(rem))
                return 0;

            set.add(rem);
            n /= 10;
        }
        return 1;
    }
    
    static void buildSetOfNumbers()
    {
        numbers.add(0);
        numbers.add(getRepeatedNumber(1));

        for (int i = 2; i < MAX + 1; i++)
            numbers.add(getRepeatedNumber(i) + numbers.elementAt(i - 1));
    }
    
    static int getNumber(int left, int right)
    {
        return numbers.elementAt(right) - numbers.elementAt(left - 1);
    }
    
    public static void main(String[] args)
    {
        int Left = 10, Right = 50;

        buildSetOfNumbers();
        System.out.println(getNumber(Left, Right));
    }
}

37

Complexity Analysis

Time Complexity

O(1) as no extra time is required.

Space Complexity

O(n) where “n” is the number of elements in the array.