Task — Represent integer

You are given a positive integer $N and a digit $D.

Write a script to check if $N can be represented as a sum of positive integers having $D at least once. If check passes print 1 otherwise 0.

Examples

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

Example 2
Input: $N = 24, $D = 7
Output: 1

Analysis

This is a tricky challenge, both to define and to execute.

As for the definition I have assumed that we are to determine whether $N can be the sum of one or more integers whose written form contains the digit $D. Each such integer may be used 0, 1 or many times in the summation.

So, let's make some observations.

Firstly, it is the case that any $N >= 10 * $D will meet that criterion. Also, if $D == 0, any $N >= 100 will do so. And for $D == 1 all positive integers will do so, because they can be written as a sum of $N 1s.

With those discoveries, the number of combinations of numbers to be added together is manageable with a recursive solution for $N in the range 0 to 10 * $D (or 0 to 100 in the case of $D == 0). For any $N beyond that range the result is 1.

And that's what I did.

Try it 

#!/usr/bin/perl

# Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge

use v5.26;    # The Weekly Challenge - 2021-05-17
use utf8;     # Week 113 - task 1 - Represent integer
use warnings; # Peter Campbell Smith
binmode STDOUT, ':utf8';
use Encode;

my ($n, @adds);

represent_integer(24, 7);
represent_integer(25, 7);
represent_integer(39, 7);
represent_integer(5, 1);
represent_integer(99, 0);

sub represent_integer {
    
    my ($d, $j, $limit);
    
    ($n, $d) = @_;
    say qq[\nInput:  \$n = $n, \$d = $d];
    $d = 10 if $d == 0;
    
    # easy answers
    if ($d <= 1 or $n >= 10 * $d) {
        say qq[Output: 1];
        return;
    }

    # get all integers < $n containing $d
    for $j ($d .. 10 * $d) {
        push @adds, $j if ($j =~ m|$d| and $j < $n);
    }
    say qq[Output: ] . add_one(0);
}

sub add_one {
    
    my ($so_far, $test);
    
    $so_far = $_[0];
    
    # try adding all the $d-matching numbers
    for $a (@adds) {
        $test = $so_far + $a;
        
        # success
        return 1 if $test == $n;
        last if $test > $n; 
        
        # recurse
        return 1 if add_one($test);
    }
    
    # no good
    return 0;
}

last updated 2026-04-03 — 20 lines of code

Output

Input:  $n = 24, $d = 7
Output: 1

Input:  $n = 25, $d = 7
Output: 0

Input:  $n = 39, $d = 7
Output: 0

Input:  $n = 5, $d = 1
Output: 1

Input:  $n = 99, $d = 0
Output: 1