Peter
Peter Campbell Smith

Divisors and digits

Weekly challenge 141 — 29 November 2021

Week 141: 29 Nov 2021

Task 2

Task — Like numbers

You are given positive integers, $m and $n. Write a script to find the total count of integers created using the digits of $m which are also divisible by $n. Repeating of digits is not allowed. The order and 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.

Examples


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.

Analysis

This seems a good time to use Algorithm::Combinatorics to generate all the combinations of the digits of $m and then use split and join and test them for divisibility by $n. The number of combinations is not very large even for quite large $n, so efficiency is not a prime objective.

Try it 

Try running the script with any input:



example: 728593



example: 13

Script


#!/usr/bin/perl

# Peter Campbell Smith - 2021-12-01
# PWC 141 task 2

use v5.20;
use warnings;
use strict;
use Algorithm::Combinatorics qw(combinations);

my (@tests, $test, $m, $n, $num_digits, @digits, $i, $iter, $c,
    $extract, $all, $good, $num_good);

# pairs of $m and $n
@tests = ([1234, 2], [768, 4], [1234567, 31]);

# loop over pairs
for $test (@tests) {
    $all = $good = '';
    $num_good = 0;
    ($m, $n) = @$test;

    # split $m into an array of digits
    $num_digits = length($m);
    @digits = split(//, $m);

    # need all the combinations of 1, 2 ... (length - 1) digits
    for $i (1..$num_digits - 1) {
        $iter = combinations(\@digits, $i);

        # loop over combinations
        while ($c = $iter->next) {

            # join digits of combination together
            $extract = join('', @$c);

            # create string of $all combs and $good combs divisible by $n
            $all .= qq[$extract, ];
            if ($extract % $n == 0) {
                $good .= qq[$extract, ];
                $num_good ++;
            }
        }
    }

    # trim trailing commas and show answer
    $all =~ s|..$||;
    $good =~ s|..$||;
    say qq[Possible integers created using the digits of $m in order are:\n$all];
    say qq[There are $num_good of these integers divisible by $n which are:\n$good\n];
}

Output

Possible integers created using the digits of 1234 
in order are:
  1, 2, 3, 4, 12, 13, 14, 23, 24, 34, 123, 124, 134, 234
There are 9 of these integers divisible by 2 which are:
  2, 4, 12, 14, 24, 34, 124, 134, 234

Possible integers created using the digits of 768 
in order are:
  7, 6, 8, 76, 78, 68
There are 3 of these integers divisible by 4 which are:
  8, 76, 68

Possible integers created using the digits of 1234567 
in order are:
  1, 2, 3, 4, 5, 6, 7, 12, 13, 14, 15, 16, 17, 23, 24,
  25 26, 27, 34, 35, 36, 37, 45, 46, 47, 56, 57, 67, 123,
  124, 125, 126, 127, 134, 135, 136, 137, 145, 146, 147,
  56, 157, 167, 234, 235, 236, 237, 245, 246, 247, 256,
  27, 267, 345, 346, 347, 356, 357, 367, 456, 457, 467,
  57, 1234, 1235, 1236, 1237, 1245, 1246, 1247, 1256,
  125, 1267, 1345, 1346, 1347, 1356, 1357, 1367, 1456,
  147, 1467, 1567, 2345, 2346, 2347, 2356, 2357, 2367,
  246, 2457, 2467, 2567, 3456, 3457, 3467, 3567, 4567,
  1245, 12346, 12347, 12356, 12357, 12367, 12456, 12457,
  2467, 12567, 13456, 13457, 13467, 13567, 14567, 23456,
  3457, 23467, 23567, 24567, 34567, 123456, 123457,
  12346, 123567, 124567, 134567, 234567
There are 4 of these integers divisible by 31 which are:
  124, 1457, 2356, 23467

 

Any content of this website which has been created by Peter Campbell Smith is in the public domain