Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Number of permutation of a particular string is divisible by a number

Tags:

algorithm

math

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)

like image 836
russell Avatar asked Nov 25 '11 09:11

russell


People also ask

How do you find if a number is divisible by any number?

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.

What are the numbers divisible by 7 from 1 to 100?

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.

How many numbers from 1 to n are divisible by all numbers from 2 to 10?

So any number divisible by 2520 is divisible by all the numbers from 2 to 10.


1 Answers

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.

like image 137
mitchus Avatar answered Nov 15 '22 08:11

mitchus