მთლიანი რიცხვები, განმეორებითი ციფრების დიაპაზონში  


Რთული ტური საშუალო
ხშირად ეკითხებიან თანამოსაყრელი ფაქტები 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 და 22 აქვთ გამეორებული ციფრები, ეს იგივეა.

იხილეთ ასევე
დაითვალეთ წყვილი, რომელთა პროდუქტები მასივშია

ვექტორს დავამატებთ რიცხვს 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

ჯავა პროგრამა მთლიანი რიცხვებისთვის, განმეორებითი ციფრების დიაპაზონში

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) რადგან დამატებითი დრო არ არის საჭირო.

იხილეთ ასევე
პროდუქტის მაქსიმალური ქვეჯგუფი

სივრცის სირთულე

O (n) სადაც "ნ" არის მასივის ელემენტების რაოდენობა.