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
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!
306 Solvers
Number of 1s in the Binary Representation of a Number
300 Solvers
Replace multiples of 5 with NaN
267 Solvers
222 Solvers
186 Solvers