주어진 숫자의 최소 배수

난이도 중급
자주 묻는 질문 얼레이션 아메리칸 익스프레스 GE 헬스 케어 퀄컴 스포티 파이
폭 우선 검색 조회수 46

숫자 0과 9로 구성된 주어진 숫자의 가장 작은 배수에서 우리는 숫자 n을 주었고, 숫자 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입니다.

주어진 숫자의 최소 배수에 대한 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는 트리를 만드는 데 사용하는 최대 노드 수입니다.

참조

Translate »