# Perl Weekly Challenge 141: Like Numbers

by Abigail ## Challenge

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.

### Example 1

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.


### Example 2

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.


## Discussion

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 0s and leading 0s? What if we have $m = 1009, and $n = 3? Some of the substrings of $m are 0, 0, 9, 00, 09,09, and009. We decide to count them all, and hence, would give7 as answer.

## Solution

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.

### Perl

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.

### Java

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.

### R

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 []

cat (substrings (list [], as.numeric (list []), -1,
as.numeric (list [])), "\n")
}


Find the full program on GitHub.

### Scheme

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 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.

### Other Languages

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