You are given positive integers,

`$m`

and`$n`

.Write a script to find total count of integers created using the digits of

`$m`

which is also divisible by`$n`

.Repeating of digits are not allowed. Order/Sequence of digits can’t be altered. You are only allowed to use (n-1) digits at the most. For example, 432 is not acceptable integer created using the digits of 1234. Also for 1234, you can only have integers having no more than three digits.

```
Input: $m = 1234, $n = 2
Output: 9
Possible integers created using the digits of 1234 are:
1, 2, 3, 4, 12, 13, 14, 23, 24, 34, 123, 124, 134 and 234.
There are 9 integers divisible by 2 such as:
2, 4, 12, 14, 24, 34, 124, 134 and 234.
```

```
Input: $m = 768, $n = 4
Output: 3
Possible integers created using the digits of 768 are:
7, 6, 8, 76, 78 and 68.
There are 3 integers divisible by 4 such as:
8, 76 and 68.
```

First, some clearification. The description says *You are only allowed to use
(n-1) digits*, but this n has no relation to `$n`

. It seems to mean the
number of digits in `$m`

. Confusing if you don't define what n is!

Second, it's unclear what *repeating of digits are
[sic] not allowed* means. If
we have `$m = 1232`

and `$n = 2`

, should we count `22`

? `2`

is repeated,
but is it the same digit? What about `12`

? Count it once, or twice?
We take the stance that if digits appear on different places in
`$m`

, we consider them as being different. So, we count `22`

, and
we count `12`

twice.

Third, what to do with `0`

s and leading `0`

s? What if we have `$m = 1009`

, and
`$n = 3`

? Some of the substrings of `$m`

are `0`

, `0`

, `9`

, `00`

, `09,`

09```
,
and
```

009`. We decide to count them all, and hence, would give`

7` as answer.

In our solutions, `n`

will refer to the **first** number, and `m`

to the
**second** number, so the other way around as in the challenge description.

We will solve this recursively. We define a subroutine `substrings`

which will count the substrings of the given number matching the specified
criteria. It takes the following arguments:

`n`

: a string. Initially called with the first number of the input.`m`

: a number. Initially called with the second number of the input; this number will passed on unmodified to recursive calls.`prefix`

: a number. This is a prefix of a constructed number so far. Initially called with`-1`

, which has as meaning "no prefix".`max`

: a number. Initially called with the first number of the input; this number will passed on unmodified to recursive calls.

The method works by removing the first character of the first argument
(`n`

), and then recursing twice: once with that character added to
the prefix, and once not.

Recursion ends if `substrings`

is called with an empty string as first
argument. `prefix`

will now be a substring of the input, and we have
to decide whether we are going to count it or not:

- If
`prefix == -1`

, we reached this by never selecting any character. We do not consider this value, so we return`0`

. - If
`prefix == max`

, we reached this by selecting all characters. This is not allowed by the challenge specification, so we return`0`

. - Otherwise, we check whether
`m`

is a proper divisor of`prefix`

(`prefix % m == 0`

), if so, we count`prefix`

and return`1`

, else, we return`0`

.

If we are recursing, in the case of selecting the first character of `n`

,
we need to calculate the new prefix. First, we set `fc`

to be the value
represented by the first character of `n`

(so `0 <= fc <= 9`

). Then,
if `prefix == -1`

, we make the recursive call with `prefix = fc`

,
else, we make the recursive call with `prefix = 10 * prefix + fc`

.

Given this, the implementations in the various languages are remarkably similar. We present a small selection.

The `substrings`

function:

```
sub substrings ($n, $m, $prefix = -1, $max = $n) {
if (!length $n) {
return $prefix > -1 &&
$prefix < $max &&
$prefix % $m == 0 ? 1 : 0;
}
my $fc = substr ($n, 0, 1);
my $n_prefix = 10 * ($prefix == -1 ? 0 : $prefix) + $fc;
substrings (substr ($n, 1), $m, $n_prefix, $max) +
substrings (substr ($n, 1), $m, $prefix, $max);
}
```

Which we call as:

```
say substrings split while <>;
```

Find the full program on GitHub.

The `substrings`

function:

```
public static int substrings (String n, int m, int prefix, int max) {
if (n . length () == 0) {
return prefix > -1 &&
prefix < max &&
prefix % m == 0 ? 1 : 0;
}
int fc = Integer . parseInt (n . substring (0, 1));
int n_prefix = 10 * (prefix == -1 ? 0 : prefix) + fc;
String tail = n . substring (1, n. length ());
return substrings (tail, m, n_prefix, max) +
substrings (tail, m, prefix, max);
}
```

And the main function:

```
public static void main (String [] args) {
Scanner scanner = new Scanner (System . in);
while (scanner . hasNextInt ()) {
int n = scanner . nextInt ();
int m = scanner . nextInt ();
System . out . println (
substrings (Integer . toString (n), m, -1, n));
}
}
```

Find the full program on GitHub.

The `substrings`

function:

```
substrings <- function (n, m, prefix, max) {
if (nchar (n) == 0) {
if (prefix > -1 && prefix < max && prefix %% m == 0) {
return (1)
}
else {
return (0)
}
}
fc <- as.numeric (substr (n, 0, 1))
tail <- substr (n, 2, nchar (n))
if (prefix < 0) {
n_prefix <- fc
} else {
n_prefix <- 10 * prefix + fc
}
return (substrings (tail, m, n_prefix, max) +
substrings (tail, m, prefix, max))
}
```

And the main program:

```
stdin <- file ('stdin', 'r')
repeat {
line <- readLines (stdin, n = 1)
if (length (line) == 0) {
break
}
parts <- strsplit (line, " ")
list <- parts [[1]]
cat (substrings (list [[1]], as.numeric (list [[2]]), -1,
as.numeric (list [[1]])), "\n")
}
```

Find the full program on GitHub.

The `substrings`

function:

```
(define (fc n) (string->number (string-take n 1)))
(define (tail n) (string-drop n 1))
(define (n_prefix prefix n) (if (= prefix -1) (fc n) (+ (* prefix 10) (fc n))))
(define (substrings n m prefix max)
(if (string-null? n)
(if (and (> prefix -1)
(< prefix max)
(= (modulo prefix m) 0)) 1 0)
(+ (substrings (tail n) m (n_prefix prefix n) max)
(substrings (tail n) m prefix max))))
```

And the main program:

```
(define (main)
(define line (read-line))
(define parts)
(if (not (eof-object? line))
(begin
(set! parts (string-split line #\ ))
(display (substrings (list-ref parts 0)
(string->number (list-ref parts 1))
-1
(string->number (list-ref parts 0))))
(newline)
(main)
)
)
)
```

Find the full program on GitHub.

We also have implementation in: AWK, Bash, C, Go, Lua, Node.js, Pascal, Python, Ruby, and Tcl.