Найменшае кратнае дадзенага ліку


Узровень складанасці серада
Часта пытаюцца ў Алацыя American Express GE Healthcare Qualcomm Spotify
Шырыня Першы пошук чаргу

У найменшым кратным дадзенага ліку, складзеным з лічбаў 0 і 9, толькі ў задачы, якую мы задалі лічбе n, знайдзіце найменшы лік, зроблены з лічбаў 0 і 9, які дзеліцца на n. Дапусцім, што адказ не перавысіць 106.

Прыкладаў

уваход
3
выхад
9

уваход
5
выхад
90

уваход
4
выхад
900

Алгарытм найменшага кратнага дадзенага ліку

Стварэнне ўсіх лікаў, утвораных толькі з дапамогай 9 і 0, падобна на атрыманне двайковых лікаў. Гэта значыць лічбы, якія змяшчаюць толькі 9 і 0, можна разглядаць як дрэва, з коранем як 9, і для кожнага вузла левы дзіця атрымліваецца шляхам дадання "0" да яго, а правы дзіця атрымліваецца шляхам дадання "9" да яго.

Найменшае кратнае дадзенага ліку

Ідэя складаецца ў тым, каб генераваць некаторыя лічбы з дапамогай абход узроўневага парадку у прыведзеным вышэй дрэве і захавайце іх у спісе перад апрацоўкай любога ўводу. Для дадзенага ліку n перабярыце сфарміраваны спіс і вярніце першы лік, які дзеліцца на n.

  1. Стварыце спіс радкоў, у якім будуць захоўвацца лічбы, якія складаюцца з 9 і 0.
  2. Стварыце чаргу з радка і націсніце на яе «9», гэта значыць корань дрэва.
  3. Выканайце цыкл ад 0 да 100, бо мы перамесцім першыя 100 вузлоў дрэва ў спіс.
  4. У кожнай ітэрацыі выдаляйце элемент з чаргі, падсоўвайце яго да спісу, дадавайце ў чаргу яго левы даччыны элемент (элемент + "0") і правы даччыны элемент (элемент + 9).
  5. Для зададзенага значэння n прайдзіце па спісе, утвораным вышэй, і вярніце першы лік, які дзеліцца на n.

У вышэйапісаным алгарытме мы ствараем дрэва, якое змяшчае элементы, зробленыя з 0 і 9, са 100 вузлоў, таму ў гэтым алгарытме значэнне maxNodes роўна 100.

Код JAVA для найменшага кратнага дадзенага ліку

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class SmallestMultipleOfAGivenNumberMadeOfDigits0And9Only {
    private static ArrayList<String> numbers = new ArrayList<>();
    private static int MAX = 100;

    private static void generateNumbers() {
        // Create a queue for level order traversal of the tree
        Queue<String> q = new LinkedList<>();
        // push the root to the queue
        q.add("9");

        // add the first MAX nodes of tree to list numbers
        for (int i = 0; i < MAX; i++) {
            // remove an element from queue
            String curr = q.poll();
            // push it to the list
            numbers.add(curr);
            // add its children to the queue
            q.add(curr + "0");
            q.add(curr + "9");
        }
    }

    private static int firstMultiple(int n) {
        try {
            // traverse in the list and return the first number divisible by n
            for (int i = 0; i < numbers.size(); i++) {
                int curr = Integer.parseInt(numbers.get(i));
                if (curr % n == 0) {
                    return curr;
                }
            }
        } catch (Exception e) {
            e.printStackTrace();
        }
        return 0;
    }

    public static void main(String[] args) {
        // pre computation
        generateNumbers();

        // Example 1
        int n1 = 3;
        System.out.println(firstMultiple(n1));

        // Example 2
        int n2 = 5;
        System.out.println(firstMultiple(n2));

        // Example 3
        int n3 = 4;
        System.out.println(firstMultiple(n3));
    }
}
9
90
900

Код C ++ для найменшага кратнага дадзенага ліку

#include <bits/stdc++.h> 
using namespace std; 

int MAX = 100;
vector<std::string> numbers;

void generateNumbers() {
    // Create a queue for level order traversal of the tree
    queue<std::string> q;
    // push the root to the queue
    q.push("9");
    
    // add the first MAX nodes of tree to list numbers
    for (int i = 0; i < MAX; i++) {
        // remove an element from queue
        string curr = q.front();
        q.pop();
        // push it to the list
        numbers.push_back(curr);
        // add its children to the queue
        q.push(curr + "0");
        q.push(curr + "9");
    }
}

int firstMultiple(int n) {
    // traverse in the list and return the first number divisible by n
    for (int i = 0; i < numbers.size(); i++) {
        int curr = stoi(numbers[i]);
        if (curr % n == 0) {
            return curr;
        }
    }
    return 0;
}

int main() {
    // pre computation
    generateNumbers();

    // Example 1
    int n1 = 3;
    cout<<firstMultiple(n1)<<endl;

    // Example 2
    int n2 = 5;
    cout<<firstMultiple(n2)<<endl;

    // Example 3
    int n3 = 4;
    cout<<firstMultiple(n3)<<endl;
    
    return 0;
}
9
90
900

Аналіз складанасці

Складанасць часу = O (maxNodes)
Складанасць прасторы = O (maxNodes)
дзе maxNodes - гэта колькасць максімальных вузлоў, з якіх мы будуем дрэва.

Спасылкі