Find smallest number formed by two digits divisible by given number

Question

I was asked the following question in an interview and I had no clue how to do it

Write a program to find the smallest number that can be formed by 0 and 9 which is divisible by a given number.
For example, if given number is 3 output should be 9, if given number is 2 output is 90, if given number is 10 output is 90

I found this solution online but I haven't understood this one bit :-

public class Smallest0And9DivisibleNumber {
    public static int find(int divisible) {
        int bin = 1;
        while (true) {
            int res = translate(bin);
            if (res % divisible == 0) {
                return res;
            }
            bin += 1;
        }
    }

    private static int translate(int bin) {
        int result = 0;
        for (int i = Integer.toBinaryString(bin).length(); i > 0; i--) {
            result *= result != 0 ? 10 : 0;
            int mask = 1 <<  (i - 1);
            result += (bin & mask) == mask ? 9 : 0;
        }
        return result;
    }

    public static void main(String[] args) {
        assert find(10) == 90;
        assert find(99) == 99;
        assert find(33) == 99;
        assert find(3) == 9;
        assert find(333) == 999;
        assert find(300) == 900;
        assert find(303) == 909;
        assert find(3033) == 9099;
        assert find(3303) == 9909;
    }
}

Can anyone please help with a good understanding or an alternative solution ?

Answer 1

This is a similar approach.

How do we do it manually for 33:

Let's go from the least number which will be? - 0. Is it divisible? No.

Let's go up a number. 9. Is it divisible? No.

Again by a number 90. Is is divisible? No.

Again by a number 99. Is it divisible? Yes.

Let's look at the pattern.

0 9 90 99

How does it look like? binary! Yes, instead of a 1 we have 9.

Now i'll go from 0 till I get a number which divides it, in the form of a binary(by replacing 1 with 9).

we get

Number Binary    0 And 9
0        0         0
1        1         9
2        10        90
3        11        99
4        100       900
5        101       909
6        110       990
7        111       999

We get all the numbers which can be formed using 0 and 9 in an ascending order.