You are given a positive integer
$Nand a digit$D.Write a script to check if
$Ncan be represented as a sum of positive integers having$Dat least once. If check passes print1otherwise0.
Input: $N = 25, $D = 7 Output: 0 as there are 2 numbers between 1 and 25 having the digit 7 i.e. 7 and 17. If we add up both we don't get 25. Input: $N = 24, $D = 7 Output: 1
We could solve this by recursion and brute force trying to find a set of numbers which to the given target number. Which will work for the baby examples with tiny, tiny numbers typical of the Perl Weekly Challenge, but would be absolutely madness for larger numbers.
Instead we will first prove that most numbers can be written as a sum of integers each containing a specific digit, and then we will prove which of the remaining numbers can.
A positive integer containing a digit \(d\) is called a \(d\)-number.
A positive integer which can be written as a sum of \(d\)-numbers is called a \(d\)-composable number.
\(N\) is \(d\)-composable if \[N \geq \begin{cases} 100, & d = 0 \\ d \cdot 10, & d \geq 1 \end{cases} \]
Let's first consider the case that \(d = 0\). If \(N \geq 100\) then we can write \(N = 100 + i + k \cdot 10\), with \(i = N \mod 10\), and \(k = \frac{N - 100 - i}{10}\).
This means we can write \(N = (100 + i) + 10 + \ldots + 10\), where we have a \(10\) \(k\) times. Since \(0 \leq i < 10\), \(100 + i\) contains a \(0\), and so does \(10\). Hence, any \(N \geq 100\) is \(0\)-composable.
If \(d > 0\) and \(N \geq 10 \cdot d\), then we can write \(N = 10 \cdot d + i + k \cdot d\), with \(i = N \mod d\), and \(k = \frac{N - 10 \cdot d - i}{d}\).
This means we can write \(N = (10 \cdot d + i) + d + \ldots + d\), where we have a \(d\) \(k\) times. Since \(0 \leq i < d\), \(10 \cdot d + i\) is a two digit number starting with a \(d\). Hence, any \(N \geq 10 \cdot d\) is \(d\)-composable.
\(N < 100\) is \(0\)-composable iff \(N\) is a multiple of \(10\).
All the \(0\)-numbers less than \(100\) are multiples of \(10\).
For \(d > 0\), \(N < 10 \cdot d\) is \(d\)-composable, iff \(N = 10 \cdot c + d \cdot k\), for some \(0 \leq c < \frac{d}{\text{gcd}(d, 10)}\).
Let \(g = \frac{d}{\text{gcd}(d, 10)}\).
If \(N < 10 \cdot d\), then \(N\) has at most two digits. It follows from the definition that if \(N\) is \(d\)-composable, then \[N = \sum_{i = 0}^{d-1} a_i \cdot (10 \cdot i + d) = 10 \cdot \sum_{i = 0}^{d-1} (a_i \cdot i) + d \cdot \sum_{i = 0}^{d-1} a_i \]
Let \(c' = \sum_{i = 0}^{d-1} (a_i \cdot i)\) and \(k' = \sum_{i = 0}^{d-1} a_i\), hence, \(N = 10 \cdot c' + d \cdot k'\), for some integers \(0 \leq c' < d, 0 < k'\).
Now, \(c' = c'' + b \cdot g\) so that \(c'' < g\) (it's possible that \(b = 0\)). Hence, \(N = 10 \cdot c'' + 10 \cdot b \cdot g + d \cdot k'\). Since \(g = \frac{d}{\text{gcd}(d, 10)}\), \(10 \cdot g\) is a multiple of \(d\). So, \(10 \cdot g = d \cdot k''\) for some integer \(k'' \geq 0\). Plugging this in, we get \(N = 10 \cdot c'' + d \cdot (k' + b \cdot k'')\). Since \(k' > 0\), we have \(N = (10 \cdot c'' + d) + d + \ldots + d\), where the number of \(d\)s is \(k' - 1 + b \cdot k''\). \(10 \cdot c'' + d\) is a one or two digit number containing a \(d\).
Picking \(c = c''\) and \(k = k' + b \cdot k''\) proofs our claim.
As an example, the table below shows all \(7\)-composable numbers below \(70\), and the break down according to the formula above:
\[ \begin{array}{rcrcl} 7 & = & & & 7 \\ 14 & = & & & 7 + 7 \\ 17 & = & 17 & & \\ 21 & = & & & 7 + 7 + 7 \\ 24 & = & 17 & + & 7 \\ 27 & = & 27 & & \\ 28 & = & & & 7 + 7 + 7 + 7 \\ 31 & = & 17 & + & 7 + 7 \\ 34 & = & 27 & + & 7 \\ 35 & = & & & 7 + 7 + 7 + 7 + 7 \\ 37 & = & 37 & & \\ 38 & = & 17 & + & 7 + 7 + 7 \\ 41 & = & 27 & + & 7 + 7 \\ 42 & = & & & 7 + 7 + 7 + 7 + 7 + 7 \\ 44 & = & 37 & + & 7 \\ 45 & = & 17 & + & 7 + 7 + 7 + 7 \\ 47 & = & 47 & & \\ 48 & = & 27 & + & 7 + 7 + 7 \\ 49 & = & & & 7 + 7 + 7 + 7 + 7 + 7 + 7 \\ 51 & = & 37 & + & 7 + 7 \\ 52 & = & 17 & + & 7 + 7 + 7 + 7 + 7 \\ 54 & = & 47 & + & 7 \\ 55 & = & 27 & + & 7 + 7 + 7 + 7 \\ 56 & = & & & 7 + 7 + 7 + 7 + 7 + 7 + 7 + 7 \\ 57 & = & 57 & & \\ 58 & = & 37 & + & 7 + 7 + 7 \\ 59 & = & 17 & + & 7 + 7 + 7 + 7 + 7 + 7 \\ 61 & = & 47 & + & 7 + 7 \\ 62 & = & 27 & + & 7 + 7 + 7 + 7 + 7 \\ 63 & = & & & 7 + 7 + 7 + 7 + 7 + 7 + 7 + 7 + 7 \\ 64 & = & 57 & + & 7 \\ 65 & = & 37 & + & 7 + 7 + 7 + 7 \\ 66 & = & 17 & + & 7 + 7 + 7 + 7 + 7 + 7 + 7 \\ 67 & = & 67 & & \\ 68 & = & 47 & + & 7 + 7 + 7 \\ \end{array} \]
Given the lemmas above, we come to the following algorithm:
$D == 0, we output 1 if $N >= 100 or $N % 10 == 0, and
0 otherwise.$D > 0, then:
$N >= 10 * $D, we output 1, else$i from 0 up to (but not including) the
greatest common divisor of $D and 10:
($N - 10 * $i - $D) is not negative, and a multiple
of $D, we output 1, and exit the loop.0.We will use an predefined array with the greatest common divisors of
10 and the numbers 1 to 9; those values are: 1, 2, 1, 2, 5, 2, 1, 2, 1.
Predefined array with greatest common divisors:
my @gcds = (0, 1, 2, 1, 2, 5, 2, 1, 2, 1);
Reading the data:
my ($N, $D) = split;
Handling the case of $D == 0:
if ($D == 0) {
say $N >= 100 || $N % 10 == 0 ? 1 : 0;
exit;
}
Handling the case where $N >= 10 * $D:
if ($N >= $D * 10) {
say 1;
exit;
}
The other cases:
for (my $i = 0; $i < $D / $gcds [$D]; $i ++) {
my $T = $N - 10 * $i - $D;
if ($T >= 0 && $T % $D == 0) {
say 1;
exit;
}
}
say 0;
Find the full program on GitHub.
The above algorithm translates practically one to one to each of the other languages we implemented the solution in: AWK, Bash, C, Lua, Node.js, Python, and Ruby.