നൽകിയ നമ്പറിന്റെ ഏറ്റവും ചെറിയ ഗുണിതം


വൈഷമ്യ നില മീഡിയം
പതിവായി ചോദിക്കുന്നു അലൈഷൻ അമേരിക്കൻ എക്സ്പ്രസ് GE ഹെൽത്ത്കെയർ ക്വാൽകോം നീനുവിനും
വീതിയുടെ ആദ്യ തിരയൽ വരി

0, 9 അക്കങ്ങൾ‌ ഉപയോഗിച്ച് നിർമ്മിച്ച ഒരു സംഖ്യയുടെ ഏറ്റവും ചെറിയ ഗുണിതത്തിൽ‌, ഞങ്ങൾ‌ ഒരു നമ്പർ‌ നൽ‌കിയ ഒരേയൊരു പ്രശ്‌നം, 0, 9 അക്കങ്ങളിൽ‌ നിന്നും നിർമ്മിച്ച ഏറ്റവും ചെറിയ സംഖ്യ കണ്ടെത്തുക, അത് n കൊണ്ട് ഹരിക്കാം. ഉത്തരം 10 കവിയരുത് എന്ന് കരുതുക6.

ഉദാഹരണങ്ങൾ

ഇൻപുട്ട്
3
ഔട്ട്പുട്ട്
9

ഇൻപുട്ട്
5
ഔട്ട്പുട്ട്
90

ഇൻപുട്ട്
4
ഔട്ട്പുട്ട്
900

നൽകിയ നമ്പറിന്റെ ഏറ്റവും ചെറിയ ഗുണിതത്തിനുള്ള അൽഗോരിതം

9 ഉം 0 ഉം മാത്രം ഉപയോഗിച്ച് രൂപംകൊണ്ട എല്ലാ അക്കങ്ങളും സൃഷ്ടിക്കുന്നത് ബൈനറി നമ്പറുകൾ സൃഷ്ടിക്കുന്നതിന് സമാനമാണ്. 9 ഉം 0 ഉം മാത്രമുള്ള അക്കങ്ങളെ a ആയി കാണാൻ കഴിയും വൃക്ഷം, റൂട്ട് 9 ആയി, ഓരോ നോഡിനും ഇടത് കുട്ടിയെ '0' ചേർത്ത് നേടുകയും വലത് കുട്ടിയെ '9' ചേർത്ത് നേടുകയും ചെയ്യുന്നു.

നൽകിയ നമ്പറിന്റെ ഏറ്റവും ചെറിയ ഗുണിതം

ഉപയോഗിച്ച് ചില സംഖ്യകൾ സൃഷ്ടിക്കുക എന്നതാണ് ആശയം ലെവൽ ഓർഡർ ട്രാവെർസൽ ഏതെങ്കിലും ഇൻ‌പുട്ട് പ്രോസസ്സ് ചെയ്യുന്നതിന് മുമ്പ് മുകളിലുള്ള ട്രീയിൽ‌ അവ ഒരു പട്ടികയിൽ‌ സംഭരിക്കുക. ഒരു നിശ്ചിത സംഖ്യ n ന്, രൂപംകൊണ്ട പട്ടികയിൽ സഞ്ചരിച്ച് ആദ്യ സംഖ്യയെ n കൊണ്ട് ഹരിക്കാം.

  1. 9, 0 എന്നിവ ഉപയോഗിച്ച് നിർമ്മിച്ച സംഖ്യകൾ സംഭരിക്കുന്ന സ്ട്രിംഗിന്റെ ഒരു പട്ടിക സൃഷ്ടിക്കുക.
  2. സ്ട്രിംഗിന്റെ ഒരു ക്യൂ സൃഷ്ടിച്ച് അതിലേക്ക് “9” പുഷ് ചെയ്യുക, അതായത് മരത്തിന്റെ റൂട്ട്.
  3. 0 മുതൽ 100 ​​വരെ ഒരു ലൂപ്പ് പ്രവർത്തിപ്പിക്കുക, കാരണം ഞങ്ങൾ ട്രീയുടെ ആദ്യത്തെ 100 നോഡുകൾ പട്ടികയിലേക്ക് തള്ളും.
  4. ഓരോ ആവർത്തനത്തിലും, ക്യൂവിൽ നിന്ന് ഒരു ഘടകം നീക്കംചെയ്‌ത് പട്ടികയിലേക്ക് തള്ളുക, അതിന്റെ ഇടത് കുട്ടിയും (ഘടകം + “0”) വലത് കുട്ടിയും (ഘടകം + “9”) ക്യൂവിലേക്ക് ചേർക്കുക.
  5. N ന്റെ ഒരു നിശ്ചിത മൂല്യത്തിനായി, മുകളിൽ‌ രൂപംകൊണ്ട പട്ടികയിൽ‌ സഞ്ചരിച്ച്, n കൊണ്ട് ഹരിക്കാവുന്ന ആദ്യ സംഖ്യ നൽകുക.

മുകളിലുള്ള അൽ‌ഗോരിതിൽ‌, 0 നോഡുകളിൽ‌ 9 ഉം 100 ഉം ഉപയോഗിച്ച് നിർമ്മിച്ച ഘടകങ്ങൾ‌ അടങ്ങിയിരിക്കുന്ന ട്രീ ഞങ്ങൾ‌ നിർമ്മിക്കുന്നു, അതിനാൽ‌ ഈ അൽ‌ഗോരിതം മാക്‍സ്‌നോഡുകളുടെ മൂല്യം 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

നൽകിയ നമ്പറിന്റെ ഏറ്റവും ചെറിയ ഒന്നിലധികം സി ++ കോഡ്

#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 (മാക്സ്നോഡുകൾ)
ബഹിരാകാശ സങ്കീർണ്ണത = O (മാക്സ്നോഡുകൾ)
ഇവിടെ ട്രീ ഉപയോഗിച്ച് ഞങ്ങൾ നിർമ്മിക്കുന്ന പരമാവധി നോഡുകളുടെ എണ്ണമാണ് മാക്സ്നോഡുകൾ.

അവലംബം