ከተሰጠ ቁጥር በጣም ብዙ  


የችግር ደረጃ መካከለኛ
ውስጥ በተደጋጋሚ ተጠየቀ የመርጨት አሜሪካን ኤክስፕረስ GE የጤና Qualcomm Spotify
ስፌት የመጀመሪያ ፍለጋ ተራ

ከቁጥር 0 እና 9 በተሰራ ቁጥር በጣም አነስተኛ በሆነ ቁጥር ውስጥ ቁጥር ሰጠነው ፣ በቁጥር 0 እና 9 የተሰራውን አነስተኛ ቁጥር በ n ሊገኝ ይችላል ፡፡ መልሱ ከ 10 እንደማይበልጥ አስቡ6.

ምሳሌዎች  

ግቤት
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 ነው ፡፡

ለተሰጠ ቁጥር በጣም አነስተኛ ለሆኑት የጃቫ ኮድ  

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

ውስብስብነት ትንተና  

የጊዜ ውስብስብነት = ኦ (ከፍተኛ ቁጥሮች)
የቦታ ውስብስብነት = ኦ (ከፍተኛ ቁጥሮች)
የ maxNodes ዛፉን የምንሠራበት ከፍተኛው አንጓዎች ቁጥር የት ነው?

ተመልከት
ክብ ሮቢን መርሐግብር ማውጣት

ማጣቀሻዎች