Suppose I have a multiset of 10 digits, for example S = { 1, 1, 2, 2, 2, 3, 3, 3, 8, 9 }
. Is there any method other than brute force to find the number of distinct permutations of the elements of S
such that when a permutation is regarded as a ten digit integer, it is divisible by a particular number n
? n
will be in the range 1
to 10000
.
For example:
if S = { 1, 2, 3, 4, 6, 1, 2, 3, 4, 6 }
and n = 10
, the result is 0
(since no permutation of those 10 digits will ever give a number divisible by 10)
if S = { 1, 1, 3, 3, 5, 5, 7, 7, 9, 2}
and n = 2
, the result is 9! / 2^4
(since we must have the 2
at the end, there are 9!
ways to permute the other elements, but there are four pairs of identical elements)
A number is divisible by another number if it can be divided equally by that number; that is, if it yields a whole number when divided by that number. For example, 6 is divisible by 3 (we say "3 divides 6") because 6/3 = 2, and 2 is a whole number.
There are 14 numbers between 1 and 100, which are exactly divisible by 7. They are 7, 14, 21, 28, 35, 42, 49, 56, 63, 70, 77, 84, 91, 98.
So any number divisible by 2520 is divisible by all the numbers from 2 to 10.
You could prune the search like so: find the prime factorization of NUM. Obviously to be divisible by NUM, a permutation needs to be divisible by all of NUM's prime factors. Hence you can use simple divisibility rules to avoid generating many invalid candidates.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With