Divisibility by $8$ for permutations of numbers
Moderator's note: This is an on-going contest problem. Per usual protocol the answers have been hidden and the question is locked until after the contest ends. (21.03.2014)
Given an integer $N$. How to check if there is a permutation of digits of integer $N$ that is divisible by $8$?
Example: Let $N = 61$ then answer is "YES" as $16$ is a permutation of $N$ that is divisible by $8$.
What's the best way to check if $N$ can be very large.
$\endgroup$ 23 Answers
$\begingroup$First, note that a number is a multiple of 8 if and only if its last three digits are a multiple of 8. So it is enough to locate, somewhere within $N$'s digits, three that can form a three-digit multiple of 8.
Now there are exactly 95 possible sets of three digits that can be rearranged to a multiple of 8, so the algorithm should have a list of them prepared ahead of time. This list $\def\L{\mathscr L}\L$ can be searched in constant time.
000 002 004 006 008 012 014 016 023 024 025 027 028 029 034 036 044 045 046 047 048 049 056 067 068 069 088 112 123 125 126 127 128 129 136 144 146 148 166 167 168 223 224 227 234 235 236 238 239 244 246 247 248 255 256 257 258 259 267 269 278 279 288 289 299 336 344 348 356 367 368 369 445 446 447 448 449 456 458 466 468 469 478 488 489 566 567 568 669 677 678 679 688 689 888
Associate with each item $i$ in $\L$ the corresponding $m(i)$ which is a multiple of 8. For example, $m(367)$ is $736$.
Associate with each item $i$ in $\L$ a number $n(i)$, initially 0. This tracks the number of digits of $i$ that have been seen in $N$. For example, if we have seen a 3 and a 7 in $N$ but not a 6, then $n(367)$ will be 2. If $n(i)$ reaches 3 for any $i$, then we know that all the digits of $i$ have all been found, and by putting them at the end in the right order, we will have a multiple of 8. (The right order is given by $m(i)$, which is computed ahead of time.)
There is a small complication because $i$ might have repeated digits, but that is not too hard to take care of. We will keep a counter $c(d)$ of the number of times each different digit is seen, for this purpose.
If $N$ has fewer then three digits, we must deal with it as a special case. (I said earlier we should pad it with zeroes; this is wrong.)
Then we scan the digits of $N$. When we see the digit $d$, increment $c(d)$.
Say that $c(d)$ now has the value $c$. Scan the elements of $\L$ looking for those that contain at least $c$ instances of digit $d$. Increment $n(i)$ for each $i$ that contains at least $c$ instances of digit $d$. (Note that when $c>3$, we can omit the scan entirely, since no item has more than 3 instances of any digit.)
If, after a scan, any item $i$ has $n(i)=3$, halt; $N$ can be permuted to a multiple of 8. If the three digits of item $i$ are abc, simply permute $N$ so that abc appear at the end in the right order as given by $m(i)$. For example, if item $i$ is 235, you need to search $N$ for a 2, a 3, and a 5, and put them at the end in the order 352. The order of the other digits does not matter.
Otherwise, after processing the last digit of $N$, halt. $N$ cannot be permuted to form any multiple of 8
This takes time proportional to the number of digits of $N$; up to a constant factor, this is optimal.
Pseudocode:
- Initialize the following variables:
L[1]...L[95] = {000, 002, 004, 006, ..., 689, 888 }as abovem[1]...m[95] = {000, 200, 040, 600, ..., 896, 888 }corresponding multiples of 8n[1]...n[95] = {0,0,...,0}, number of digits ofL[i]that have been seen so farc[0]...c[9] = {0,0,0,0,0,0,0,0,0,0}number of instances of digit $d$ that have been seen so far
And suppose that $N$ is an $n$-digit number whose digits are in N[1]...N[n].
for i in 1 to n do: d ← N[i] c[d] ← c[d]+1 if c[d] < 4 then: for j from 1 to 95 do: if L[j] has at least c[d] copies of digit d: n[j] ← n[j] + 1 If n[j] = 3 HALT and output "yes" and the value of m[j] end if end for j end if end for iHALT and output "no"
The value of $m[j]$ emitted with "yes" tells you which three digits of $N$ to move to the end to obtain a multiple of 8.
A more efficient algorithm replaces the repeated linear scan of $\L$ with a preselection of 30 sublists, with sublist $10a+b$ containing all the elements of $\L$ that have at least $a+1$ occurrences of digit $b$. But this and other such optimizations are engineering details.
$\endgroup$ 16 $\begingroup$Criterion of divisibility by 8: the integer formed with the last 3 digits is divisible by 8.
Now if $N$ is large, try to find 3 digits to create a number with this particularity.
$\endgroup$ 9 $\begingroup$We can use a divisibility rule for 8:
Let $n=\ldots a_4a_3a_2a_1$.
- If $a_3$ is even, then $n$ is divisible by 8 if $a_2a_1$ is divisible by 8.
- If $a_3$ is odd, then $n$ is divisible by 8 if $a_2a_1$ is divisible by 4 but not 8.
The two digit numbers divisible by 8 are
00, 08, 16, 24, 32, 40, 48, 56, 64, 72, 80, 88, 96,
and the two digit numbers divisible by 4 but not 8 are
04, 12, 20, 28, 36, 44, 52, 60, 68, 76, 84, 92.
Thus a number with three or more digits has a permutation by its digits that is divisible by 8 if it
- contains a pair of digits present in the first list and at least one other digit that is even,
or if it
- contains a pair of digits present in the second list and at least one other digit that is odd.
Thus the number 6295 has such a permutation (9256), since it contains the digits 6 and 5 (as in 56) and the even number 2.
By the way, this would be soo much easier if we were checking for divisibility by 3 ;P
$\endgroup$ 2
