Укупан број без поновљених цифара у опсегу


Ниво тешкоће Средњи
Често питани у Аццолите Фацтсет МАК
Математика Бројеви-цифре

Добија се низ бројева (почетак, крај). Дати задатак каже да се сазна укупан број бројева без поновљених цифара у опсегу.

Пример

Улаз:

10 50

Излаз:

37

objašnjenje:

10 нема поновљену цифру. 11 има поновљену цифру. 12 нема поновљену цифру. док 22, 33 има поновљену цифру. Дакле, када смо пронашли бројеве који немају поновљену цифру, то ћемо рачунати у наш резултат.

Укупан број без поновљених цифара у опсегу

Алгоритам

  1. Изјавите а Сет и вектор.
  2. Гурните 0 и 1 у вектор и сазнајте све факторе у року од 10, а остатке сачувајте у скупу. Ако скуп већ садржи тај број ретурн 0 елсе ретурн 1.
  3. Узми тај број и додај га у вектор.
  4. За сваки упит вратите разлику вектора [крај] и вектора [почетак].

Објашњење за укупне бројеве без поновљених цифара у опсегу

Дали смо опсег. Затражили смо да сазнамо како укупан број броја који долази у датом опсегу нема поновљену цифру у самом броју. За ово ћемо користити оквир сакупљања. Користићемо скуп и вектор. Сет служи за чување неуобичајених фактора или остатка броја, а вектор за чување броја филтрираног из скупа. Знамо да се мало њих само број на било којем месту од 10 цифара не понавља, као од 1 до 10, нема броја који се понавља. Од 11 до 10 и од 21 до 30, постоје два броја која понављају цифре као 11 и 22, ово иде исто.

У вектор ћемо додати бројеве 0 и 1, од вредности 2 до дате вредности, каква год она била. Добијте број који има фактор или остатак у смислу 10, као што је горе поменуто. Добићемо те остатке и додати их у скуп ако скуп већ садржи тај број као остатак. Ретурн 0 елсе додај тај остатак скупу. Како ће то бити нови број или остатак и вратит ће се 1. Наставите да се крећете док вредност не постане 0. Овде ћемо добити број из отприлике 0 или 1, и додати га заједно са бројем који га преузима кроз вектор, и притиснути цоунт до самог вектора.

За сваки упит који се даје вратићемо разлику бројева на десној позицији, што значи десни опсег, а бројеви на левој позицији означавају број на левој опсегу у вектору. Вратићемо ову разлику, ово ћемо бити тражени одговор.

Имплементација

Ц ++ програм за укупне бројеве без поновљених цифара у опсегу

#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

Јава програм за укупне бројеве без поновљених цифара у опсегу

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

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

Сложеност времена

О (1) јер није потребно додатно време.

Сложеност простора

Он) где „Н“ је број елемената у низу.