একটি ব্যাপ্তিতে কোনও পুনরাবৃত্তি সংখ্যা ছাড়াই মোট সংখ্যা


কাঠিন্য মাত্রা মধ্যম
প্রায়শই জিজ্ঞাসা করা হয় সমষ্টি ফ্যাক্সেট ম্যাক
ম্যাথ সংখ্যা-সংখ্যা

আপনাকে সংখ্যার পরিসর দেওয়া হবে (শুরু, শেষ)। প্রদত্ত টাস্কটি বলছে যে কোনও পরিসরে কোনও পুনরাবৃত্ত সংখ্যা ছাড়াই সংখ্যার মোট সংখ্যা বের করতে।

উদাহরণ

ইনপুট:

10 50

আউটপুট:

37

ব্যাখ্যা:

10 এর কোনও পুনরাবৃত্ত অঙ্ক নেই। 11 এর পুনরাবৃত্তি সংখ্যা রয়েছে। 12 এর কোনও পুনরাবৃত্তি সংখ্যা নেই। যেখানে 22, 33 এর পুনরাবৃত্তি সংখ্যা রয়েছে। সুতরাং যখন আমরা এমন সংখ্যাগুলি খুঁজে পেয়েছি যার কোনও পুনরাবৃত্ত সংখ্যা নেই, আমরা আমাদের ফলাফলটিতে এটি গণনা করব।

একটি ব্যাপ্তিতে কোনও পুনরাবৃত্তি সংখ্যা ছাড়াই মোট সংখ্যা

অ্যালগরিদম

  1. ঘোষণা করুন ক সেট এবং একটি ভেক্টর
  2. 0 এবং 1 টি ভেক্টরে চাপুন এবং 10 এর মেয়াদে সমস্ত কারণগুলি খুঁজে বের করুন এবং অবশিষ্টাংশগুলিকে সেটে সংরক্ষণ করুন। যদি সেটটিতে ইতিমধ্যে সেই সংখ্যাটি থাকে তবে 0 টি ফিরে আসুন।
  3. এই নম্বরটি পান এবং এটিতে যুক্ত করুন ভেক্টর.
  4. প্রতিটি প্রশ্নের জন্য, ভেক্টর [শেষ] এবং ভেক্টর [শুরু] এর পার্থক্যটি ফিরিয়ে দিন।

একটি পরিসরে কোনও পুনরাবৃত্তি সংখ্যা ছাড়াই মোট সংখ্যাগুলির জন্য ব্যাখ্যা

আমরা একটি পরিসীমা দিয়েছে। আমরা প্রদত্ত পরিসরে যে সংখ্যাটি আসে তার মোট সংখ্যাটি সন্ধান করতে বলেছি number সংখ্যাটিতে নিজেই কোনও পুনরাবৃত্ত সংখ্যা নেই। এই জন্য, আমরা সংগ্রহ কাঠামো ব্যবহার করতে যাচ্ছি। আমরা সেট এবং ভেক্টর ব্যবহার করব। সেটটি হ'ল কোনও সংখ্যার অস্বাভাবিক উপাদান বা বাকীটি সঞ্চয় করতে হয় এবং ভেক্টর সেট থেকে ফিল্টার করা নম্বরটি সংরক্ষণ করতে হয়। আমরা জানি যে কোনও দশকের দশকের জায়গায় কেবল কয়েকটি সংখ্যারই পুনরাবৃত্তি হয় না, যেমন 10 থেকে 1 এর মধ্যে কোনও পুনরাবৃত্তি সংখ্যা নেই। 10 থেকে 11 এবং 10 থেকে 21 পর্যন্ত, দুটি সংখ্যা রয়েছে যেগুলি 30 এবং 11 হিসাবে পুনরাবৃত্ত সংখ্যাগুলি করেছে, এটি একই হয়।

আমরা ভেক্টরের সাথে 0 এবং 1 নম্বরটি যোগ করা করব, মান 2 থেকে প্রদত্ত মান, যাই হোক না কেন, যোগ করব। উপরে উল্লিখিত হিসাবে 10 এর শর্তে একটি ফ্যাক্টর বা বাকী রয়েছে এমন নম্বরটি পান। আমরা সেই অবশিষ্টাংশগুলি পেয়ে যাব এবং সেটটিতে যোগ করব যদি সেটটিতে ইতিমধ্যে অবশিষ্টটি থাকে। 0 তে ফিরে আসুন এবং সেটির বাকি অংশটি সেটে যুক্ত করুন। যেহেতু এটি একটি নতুন সংখ্যা বা বাকী থাকবে এবং ফিরে আসবে 1. মান 0 হওয়ার আগ পর্যন্ত ট্র্যাভার্স করে চলুন Here এখানে আমরা 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) কোন অতিরিক্ত সময় প্রয়োজন হয় হিসাবে।

স্পেস জটিলতা ity

উপর) কোথায় "এন" অ্যারেতে উপাদানগুলির সংখ্যা।