# Hackerrank Solution: Special Multiple

Original Problem

You are given an integer $$N$$. Can you find the least positive integer $$X$$ made up of only 9's and 0's, such that, $$X$$ is a multiple of $$N$$? $$X$$ is made up of one or more occurences of 9 and zero or more occurences of 0.

## Input Format

The first line contains an integer $$T$$ which denotes the number of test cases. $$T$$ lines follow.Each line contains the integer $$N$$ for which the solution has to be found.

## Output Format

Print the answer $$X$$ to STDOUT corresponding to each test case. The output should not contain any leading zeroes.

## Constraints

• $$1 \leq T \leq 10^4$$
• $$1 \leq N \leq 500$$

## Solution

The main task here is to find a way to generate reasonable permutations of 0 and 9 to check if they divide $$N$$, that is $$\{9, 90, 99, 900, 909, \dots\}$$. Since we want the least number that divides $$N$$ and have two digits, we can generate the sequence from $$1$$ to $$\infty$$ in binary and multiply the resulting number by 9. The first number that divides $$N$$ must be the least this way. An implementation in JavaScript is then just the following code - using JavaScripts ability to implicitly cast a string to a number when multiplying:

function solve(n) {

for (let i = 1; ; i++) {
let x = 9 * i.toString(2);
if (x % n == 0) {
return x;
}
}
}

« Back to problem overview