Number formation from given digits I was asked this question in a recent interview. You are given two digits $0$ and $9$. Using only these two digits you must form the least positive number that is a multiple of a given '$n$' . The value of $n$ will be provided before hand. For example if we are given $n$ as $7$ then the answer will be $9009$ .

I tried using some basic divisibility principles but was not able to come up with a correct solution and code it up. Probably I need some help in number theory
The simplest solution is to use a recurrence:

Let $f(k,x) \Leftrightarrow \text{There is a number with k digits made of 0s and 9s that is equal to x modulo n}$

Then it is not hard to compute $f(k,x)$ using $\{ f(k-1,y) : y \in [0..n-1] \}$

This algorithm takes $O(cn)$ time where $c$ is the number of digits in the answer. From intuition I would guess that $c$ is generally $O(\log(n))$.
Start with $9$. Divide this by $n$ and take the remainder. Call the remainder $R$. If $n$ divides $10R+9$ then add the digit 9 and you are done. If not add the digit $0$ and divide $10 R$ by $n$ and take the remainder. Repeat the process.

The proof of this follows from the observation: If we have a number $X$ and add an extra digit $Y$ then the new number is $10X + Y$ and the new remainder is obtained by dividing $10 R+ Y$.

In your example:

$$
 9 = 1 \times 7 + 2 ~~~ R=2, ~~\text {7 does not divide $2\times 10  +9$}\\
 2\times 10 = 2 \times 7 + 6 ~~ R = 6, ~~\text {7 does not divide $6\times 10 +9$}\\
 6 \times 10 = 8 \times 7 + 4 ~~ R = 4, ~~ \text {7 divides $4\times 10 + 9$}\\
$$
So the answer is $9009$

Added as after thought

This is the smallest number of the form $900\cdots 09$. Not sure if there is a simple way to find the answer. For example, if $n$ is 367, then the answer is $9909$ but there is no simple way to find it other than some form of a $\alpha-\beta$ pruning.