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;
    }
  }
}