How many permutations of an array when created into a number are divisible by 4 or 8?

Question

We have an array of numbers ex. {0, 5, 4, 8, 9}. We have to find the number of permutations that when the array is turned into a number (ex. {6, 8, 3, 2} -> 6832) the number will be divisible by 4. The number of elements of the vector will be max. 17 so I just need to find an exponentional algorithm. I've tried lots of different methods and settled on finding "pairs" of numbers but I'm interested is there a less sanity-destroying method that will work also for ex. numbers divisible by 8.

Answer 1

A number can be divisible by four if and only if the number formed by its last two digits are divisible by four. We can disregard eight since anything divisible by eight is also divisible by four.

Say your array, A, has size n.

1. Count the 2+ digit numbers that are divisible by 4. Say this is k. Having any of these at the end results in a number divisible by 4, so these contribute k * (n-1)! to the total.

2. If there are any even 1 digit numbers

2a. Count the 1-digit numbers congruent to 0 mod 4.

2b. Count the 1-digit numbers congruent to 2 mod 4.

2c. Count all even numbers

2d. Note that n - (count of even numbers) is the count of odd numbers.

2e. Add (n-2)! * (2a * (2c - 1)) to the total.

2f. Add (n-2)! * (2b * 2d) to the total.

This works because the valid predecessors of a last digit d are:

if d mod 4 is 0: 0, 2, 4, 6, 8
if d mod 4 is 2: 1, 3, 5, 7, 9
otherwise: n/a

in your example [0,5,4,8,9]:

1. 0: there are no 2+ digit numbers

2a. There are 3 digits congruent to 0 mod 4: 0, 4, 8

2b. There are 0 digits congruent to 2 mod 4

2c: There are 3 even numbers: 0, 4, 8

2d: There are 2 odd numbers: 5, 9

Here, our total is 0 + 6 * 3 * 2 + 6 * 0 * 2 = 36