دیئے گئے نمبر کا سب سے چھوٹا ایک سے زیادہ


مشکل سطح درمیانہ
اکثر پوچھا جاتا ہے اییلیشن امریکن ایکسپریس GE صحت کا خیال Qualcomm Spotify
چوڑائی پہلی تلاش قطار

ہندسوں 0 اور 9 کے صرف دیئے گئے مسئلے کی سب سے چھوٹی سی کثیر میں ، جس میں ہم نے ایک نمبر دیا ہے ، 0 اور 9 کے ہندسوں سے بننے والی سب سے چھوٹی نمبر تلاش کریں جو n کے ذریعہ تقسیم ہے۔ فرض کریں کہ جواب 10 سے زیادہ نہیں ہوگا6.

مثال کے طور پر

ان پٹ
3
آؤٹ پٹ
9

ان پٹ
5
آؤٹ پٹ
90

ان پٹ
4
آؤٹ پٹ
900

دیئے گئے نمبر کے چھوٹے چھوٹے ایک سے زیادہ کیلئے الگورتھم

صرف 9 اور 0 کا استعمال کرتے ہوئے تشکیل پانے والے تمام نمبروں کو بنانا بائنری نمبر تیار کرنے کے مترادف ہے۔ یہ صرف 9 اور 0 پر مشتمل نمبروں کو بطور a دیکھا جاسکتا ہے درخت، جڑ کے طور پر 9 اور ہر نوڈ کے لئے بائیں بچے کو اس میں '0' شامل کرکے حاصل کیا جاتا ہے اور دائیں بچے کو اس میں '9' شامل کرکے حاصل کیا جاتا ہے۔

دیئے گئے نمبر کا سب سے چھوٹا ایک سے زیادہ

خیال یہ ہے کہ استعمال کرکے کچھ نمبر تیار کریں سطح کا آرڈر پار کرنا اوپر درخت میں اور ان پٹ پر کارروائی کرنے سے پہلے ان کو ایک فہرست میں اسٹور کریں۔ دیئے گئے نمبر ن کے ل formed ، تشکیل شدہ فہرست میں سے عبور کریں اور پہلی تعداد کو n کے ذریعہ تقسیم کرنے والے کو واپس کریں۔

  1. تار کی ایک فہرست بنائیں جو 9 اور 0 سے بنی نمبروں کو محفوظ کرے گی۔
  2. تار کی قطار بنائیں اور اس پر "9" ، یعنی درخت کی جڑ کو دبائیں۔
  3. 0 سے 100 تک لوپ چلائیں ، کیوں کہ ہم درخت کے پہلے 100 نوڈس فہرست میں ڈالیں گے۔
  4. ہر تکرار میں ، کسی عنصر کو قطار سے ہٹائیں ، اسے فہرست میں دبائیں ، اس کے بائیں بچے (عنصر + “0”) اور دائیں بچے (عنصر + “9”) کو قطار میں شامل کریں۔
  5. ن کی دی گئی قیمت کے ل above ، اوپر تشکیل دی گئی فہرست میں سے عبور کریں ، اور 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

دیئے گئے نمبر کے چھوٹے چھوٹے ایک سے زیادہ کیلئے 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 (میکس نوڈس)
خلائی پیچیدگی = O (میکس نوڈس)
جہاں میکس نوڈس زیادہ سے زیادہ نوڈس کی تعداد ہے جس کے ساتھ ہم درخت بناتے ہیں۔

حوالہ جات