श्रेणीमध्ये पुनरावृत्ती होणारे अंक नसलेले एकूण क्रमांक


अडचण पातळी मध्यम
वारंवार विचारले एकत्रित फॅक्टसेट एमक्यू
गणित संख्या-अंक

आपल्‍याला संख्येची श्रेणी दिली गेली आहे (प्रारंभ, शेवट) दिलेली कार्ये श्रेणीमध्ये पुनरावृत्ती न करता अंकांची एकूण संख्या शोधण्यासाठी सांगते.

उदाहरण

इनपुट:

10 50

आउटपुट:

37

स्पष्टीकरण:

10 चा कोणताही अंक नाही. 11 चा पुनरावृत्ती अंक आहे. 12 चा कोणताही अंक नाही. तर 22, 33 चा अंक वारंवार आहे. जेव्हा आपल्याला अशी अंक सापडतील की ज्यामध्ये पुनरावृत्ती होणारा अंक नसेल तर आम्ही आमच्या निकालात ती मोजू.

श्रेणीमध्ये पुनरावृत्ती होणारे अंक नसलेले एकूण क्रमांक

अल्गोरिदम

  1. घोषित ए सेट करा आणि एक वेक्टर
  2. 0 आणि 1 वेक्टर मध्ये ढकलणे आणि 10 च्या मुदतीत सर्व घटक शोधा आणि उर्वरितांना संचात साठवा. सेटमध्ये आधीपासून तो नंबर परतावा असल्यास 0 परतावा 1.
  3. तो नंबर मिळवा आणि त्यामध्ये जोडा वेक्टर.
  4. प्रत्येक क्वेरीसाठी, वेक्टर [एंड] आणि वेक्टर [प्रारंभ] मधील फरक परत करा.

श्रेणीमध्ये पुनरावृत्ती होणारे अंक नसलेल्या एकूण क्रमांकाचे स्पष्टीकरण

आम्ही एक श्रेणी दिली आहे. आम्ही दिलेल्या श्रेणीत येणा the्या संख्येची संख्या शोधण्यासाठी विचारले आहे की त्या संख्येमध्ये स्वतःला कोणताही अंक नाही. त्यासाठी आम्ही संकलनाची चौकट वापरणार आहोत. आम्ही सेट आणि वेक्टर वापरणार आहोत. सेट म्हणजे असामान्य घटक किंवा संख्येचा उर्वरित भाग संग्रहित करायचा असतो आणि सेटमधून फिल्टर केलेल्या नंबरचा संग्रह वेक्टर असतो. आम्हाला माहित आहे की 10 पैकी 1 अंकाच्या स्थानांपैकी केवळ काहीच पुनरावृत्ती होत नाहीत, जसे 10 ते 11 पर्यंत पुनरावृत्ती क्रमांक नाही. ११ ते १० आणि २१ ते From० या कालावधीत, दोन आणि ११ आणि २२ अशी पुनरावृत्ती होणारी दोन संख्या आहेत.

आम्ही व्हॅक्टर 0 वरून दिलेल्या व्हॅल्यू पर्यंत 1 आणि 2 व्हॅक्टर जोडू शकतो. वर नमूद केल्याप्रमाणे 10 च्या बाबतीत घटक किंवा उर्वरित क्रमांक मिळवा. आम्ही ते उर्वरित मिळवू आणि सेटमध्ये आधीपासूनच उर्वरित म्हणून हा नंबर असल्यास सेटमध्ये समाविष्ट करू. 0 परत जा आणि उर्वरित सेटमध्ये जोडा. जसे की ही एक नवीन संख्या किंवा उर्वरित असेल आणि परत येईल 1. मूल्य 0 होईपर्यंत फिरत रहा. येथे आपल्याला 0 किंवा 1 सारख्या नंबर मिळतील आणि ते एका व्हॅक्टरद्वारे मिळविणा number्या संख्येसह जोडू आणि गणना दाबा. स्वत: वेक्टरला.

प्रत्येक क्वेरी द्या, आम्ही संख्येचा फरक योग्य स्थानावर परत करत आहोत, म्हणजेच उजवी श्रेणी, आणि डाव्या स्थानावरील संख्या म्हणजे वेक्टरमधील डाव्या श्रेणीतील संख्या. आम्ही हा फरक परत करू, आम्ही हेच आवश्यक उत्तर असेल.

अंमलबजावणी

श्रेणीमध्ये पुनरावृत्ती होणारे अंक नसलेल्या एकूण क्रमांकासाठी सी ++ प्रोग्राम

#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) कोणताही अतिरिक्त वेळ आवश्यक नसल्यामुळे.

स्पेस कॉम्प्लेक्सिटी

O (n) जेथे “एन” अ‍ॅरे मधील घटकांची संख्या.