Всего чисел без повторяющихся цифр в диапазоне


Сложный уровень средний
Часто спрашивают в Акколит Набор фактов MAQ
Математики Число-цифры

Вам дается диапазон чисел (начало, конец). В данной задаче сказано узнать общее количество чисел без повторяющихся цифр в диапазоне.

Пример

Входной сигнал:

10 50

Вывод:

37

Объяснение:

10 не имеет повторяющейся цифры. 11 имеет повторяющуюся цифру. 12 не имеет повторяющейся цифры. тогда как 22, 33 имеет повторяющуюся цифру. Поэтому, когда мы найдем числа, у которых нет повторяющейся цифры, мы посчитаем это в нашем результате.

Всего чисел без повторяющихся цифр в диапазоне

Алгоритм

  1. Объявить Набор и вектор.
  2. Вставьте 0 и 1 в вектор и найдите все множители в 10, а остатки сохраните в наборе. Если набор уже содержит это число, верните 0, иначе верните 1.
  3. Получите это число и добавьте его в вектор.
  4. Для каждого запроса вернуть разницу между вектором [конец] и вектором [начало].

Объяснение общего числа без повторяющихся цифр в диапазоне

Мы дали диапазон. Мы попросили выяснить, что общее число числа, которое входит в данный диапазон, не имеет повторяющейся цифры в самом числе. Для этого мы собираемся использовать фреймворк коллекций. Мы будем использовать набор и вектор. Набор предназначен для хранения необычных факторов или остатка числа, а вектор - для хранения числа, отфильтрованного из набора. Мы знаем, что некоторые из них не повторяются только число в любом месте десяти цифр, например, от 10 до 1, нет повторяющегося числа. От 10 до 11 и от 10 до 21 есть два числа, которые имеют повторяющиеся цифры, такие как 30 и 11, это то же самое.

Мы добавим в вектор числа 0 и 1, от значения 2 до данного значения, каким бы оно ни было. Получите число, имеющее множитель или остаток в виде 10, как упомянуто выше. Мы получим эти остатки и добавим в набор, если набор уже содержит это число в качестве остатка. Вернуть 0, иначе добавить этот остаток в набор. Так как это будет новое число или остаток и возврат 1. Продолжайте перемещаться, пока значение не станет 0. Здесь мы получим число, подобное 0 или 1, и сложим его с числом, получая его через вектор, и подтолкнем счетчик. к самому вектору.

Для каждого запроса мы будем возвращать разность чисел в правой позиции, что означает правый диапазон, а числа в левой позиции означают число в левом диапазоне вектора. Мы вернем эту разницу, это будет нам требуемый ответ.

Реализация

Программа на C ++ для общего числа без повторяющихся цифр в диапазоне

#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 для общего числа без повторяющихся цифр в диапазоне

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

Анализ сложности

Сложность времени

O (1) так как дополнительного времени не требуется.

Космическая сложность

О (п) в котором «Н» это количество элементов в массиве.