Smallest Multiple of a Given Number


Difficulty Level Medium
Frequently asked in Alation American Express GE Healthcare Qualcomm Spotify
Breadth First Search Queue

In the smallest multiple of a given number made of digits 0 and 9 only problem we have given a number n, find the smallest number made from digits 0 and 9 that is divisible by n. Assume that the answer will not exceed 106.

Examples

Input
3
Output
9

Input
5
Output
90

Input
4
Output
900

Algorithm for Smallest Multiple of a Given Number

Generating all the numbers formed using only 9 and 0 is similar to producing binary numbers. That is the numbers containing only 9 and 0 can be viewed as a tree, with root as 9 and for every node the left child is obtained by appending ‘0’ to it and right child is obtained by appending ‘9’ to it.

Smallest Multiple of a Given Number

The idea is to generate some numbers using the level order traversal in above tree and store them in a list before processing any input. For a given number n, traverse in the list formed and return the first number divisible by n.

  1. Create a list of string that will store the numbers made up of 9 and 0.
  2. Create a queue of string and push “9” to it, that is, the root of the tree.
  3. Run a loop from 0 to 100, as we will push first 100 nodes of the tree to the list.
  4. In every iteration, remove an element from queue, push it to the list, add its left child(element + “0”) and right child(element + “9”) to the queue.
  5. For a given value of n, traverse in the list formed above, and return the first number divisible by n.

In the above algorithm, we build the tree containing elements made with 0 and 9, of 100 nodes, so in this algorithm the value of maxNodes is 100.

JAVA Code for Smallest Multiple of a Given Number

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++ Code for Smallest Multiple of a Given Number

#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

Complexity Analysis

Time Complexity = O(maxNodes)
Space Complexity = O(maxNodes)
where maxNodes is the number of maximum nodes we build the tree with.

References