# Smallest Multiple of a Given Number

Difficulty Level Medium
Frequently asked in Alation American Express GE Healthcare Qualcomm Spotify

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.

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. 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.Queue;

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
// push the root to the queue

// 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
// add its children to the queue
}
}

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

Translate »