A "Pandigital number of order X" is one that contains all of the numbers from 0 to X, but with no leading zeroes. If X>9, the cycle 0-9 repeats itself. For example, 2310 is a Pandigital number of order 3 (0-3), while 120345678901 is a Pandigital number of order 11, with the "01" at the end of the number representing 10 and 11, respectively (10 and 11 mod 10, essentially). 0321 is not a Pandigital number, as it has a leading zero.
Given a number X, determine how many pandigital numbers of that order are divisible by 11. You do not need to return the numbers themselves, just how many of them there are.
I don't think the case for x > 9 is handled correctly. Consider x = 11. My interpretation is that a pandigital number of order 11 will contain exactly two 0's, two 1's and one of every digit 2 through 9. Using a brute force approach, I can check every pandigital number of order 11 and see if it is a multiple of 11:
count = 0;
digs = 0:11;
for d0 = 1:9
strs = unique(perms(char(mod(setdiff(digs, d0), 10) + '0')), 'rows');
nums = str2num([repmat(char(d0 + '0'), size(strs, 1), 1) strs]);
count = count + sum(mod(nums, 11) == 0);
end
Quite simply, this loops over each starting digit, except zero, takes all possible unique permutations of the remaining digits, then counts the number divisible by 11. This yields a solution of 9072000.
Note that this approach is not a suitable answer for Cody, since its runtime is on the order of an hour, but is the simplest way to demonstrate a correct solution for x = 11.
Reggie, I think you may be right, and I think I know what the issue is with my test cases. Sadly, I can't check out my suspicions yet; the machine I need to use with enough memory for a brute force test for x=11 is currently using all 12 cores running very long calculations which are using up about 85% of the available memory. I've disabled the X>9 cases in the solution set for now until I can double check them, so the problem should be much easier now. If your solution works for X<10, go ahead and submit.
to add to the confusion, my (non-brute-force) approach leads to the following counts N(10)=2,246,400 N(11)=22,896,000 and N(14)=26,714,545,200
My combinatoric approach and brute force method both agree for x = 10 with 1454400 and for x = 11 with 9072000. I can't brute force beyond that, but an reasonably I am handling the redundant permutations introduced when we have duplicate digits due to these two cases. For reference, I get 3216477600 for x = 14.
my mistake, my results now match those reported by Reggie, I get N(10)=1,454,400, N(11)=9,072,000, and N(14)=3,216,477,600.
I figured out what the issue was with the code I was using for the test suite - I neglected to put in the check in to make sure that the first set of numbers I was checking hadn't already been calculated by the code. It wasn't a problem when there were no repeats (X9, repeats started occuring. Since 1-2-3-4-0 and 1-2-3-0-4 were both checked and calculated, that made my values higher than they should have been. (Short version - I forgot a "unique" command.) On the bright side, going through the code line-by-line to figure out what was going on allowed me to make it much, much faster.
And now we know why this one is a hard problem! :-)
Quite right James! It took me some time to fix the repeating combinations error, but it was worth :D
I just feel better knowing that even Alfonso messed up a bit on this one. If he can screw up, what chance do we mere mortals have? ;-)
Project Euler solution for x=19.
It was a real nightmare for me.
Thank you James
Please correct me if I'm wrong. How come pandigitalby11(6)>0. Since the sum of its digits is 21, which can never by a multiple of 11.
Never mind my comment xD
This one took a while.
wow, I am very impressed! (just for completion, if I am interpreting correctly for x>=20 I believe you would need to have a prod(factorial(histcounts... instead of prod(histcounts..., right?)
Yes, you're right. :-)
Test suite changed to prevent solutions like this one.
Test suite changed to try to prevent solutions like this one.
Does the problem statement have a typo?, it says 2310 is a pandigital number of order 4, but it should be 3, right?
You are correct, Daniel. The typo has been fixed. Thanks for pointing that out!