Pandigital Number (Need understanding of a particular logic)

[Ranajoy Saha]

Hi, everyone

I found a piece of code on the web in which the quickest possible way to know whether a number is a pandigital number can be know. We shall say that an n-digit number is pandigital if it makes use of all the digits 1 to n exactly once. For example, 2143 is a 4-digit pandigital and is also prime. The logic I had in mind was to run a loop, initializing it with 0 and running it through 9 and the checking if a number had it's occurrence more than one time and then return that it is not a pandigital number, but the code I saw did the same work with larger digit numbers within 210ms as was mentioned while handling 7 digit number.
The code is as follows

public boolean isPandigital(long n) {
            int digits = 0;
            int count = 0;
            int tmp;

            while (n > 0) {
                tmp = digits;
                System.out.println("tmp " + tmp);
                digits = digits | 1 << (int)((n % 10) - 1); //The minus one is there to make 1 fill the first bit and so on
                System.out.println("digits " + digits);
                if (tmp == digits) { //Check to see if the same digit is found multiple times
                    return false;
                }

                count++;
                n /= 10;
            }

            return digits == (1 << count) - 1;
        }

I dont need understanding of the value returned by this method but the logic behind it. No matter which ever number I try (I tried with 1234567899) it gave me false and the build time by NetBeans was just 0 seconds "BUILD SUCCESSFUL (total time: 0 seconds)". This method is really very fast and I am eager to know the truth behind it. Please help me out. Any help is appreciated. The link to the website from where I found the code is http://www.mathblog.dk/project-euler-41-pandigital-prime/

Regards,
Ranajoy

[Mike. J. Thompson]

Well firstly the build time that netbeans is showing is the amount of time it took to compile, not running time of the method. I don't know the resolution its using to count the time, but I suspect it rounds down, so any build time less than one second is reported as zero seconds.

Now to the logic of that method. It is using the first 'n' bits in an int to represent each of the digits in the number (where 'n' is the number of digits).

It extracts each digit in turn, and then sets the corresponding bit to 1. So if the digit is 1 it sets the first bit to 1, and if the digit is 9 it sets the 9th bit to 1.

It keeps a track of the previous state of the bits, and if the new state equals the previous state then it knows that the last digit was a duplicate of a digit already seen.

[Piet Souris]

hi Ranajoy,

I must admit: it is a very nice way to discover a pandigital.

What happens here is that this method puts a '1' on bit location n-1, given a current digital of n.
If it then is working on a digital t, it checks if bit number t-1 is a '1' or not. If it is a '1', that
means it has seen this digit before, so the number in question cannot be a pandigital.

I guess this sounds pretty unclear. So let's try an example. Say, the number in question is 424.

Now, in the first pass, digits = 0, and so is tmp. Then follows the trick.
First, the last digit is determined, i.e. 4, by the standard method: digit = n % 10.
Then, it takes 1, shifts it (4 - 1) = 3 places to the left, and 'OR''s it with digits.

digits now becomes the binary '1000'.

So, in effect, it puts a '1' in the fourth place from the right, using the bits in 'digits'
as an array.

Then it does: n = n / 10. So n = 42.

The last digit now is 2. So it shifts a '1' one (2 - 1) place to the left, we then get the number '10'
(in binary), and 'OR's it with digits, giving the number '1010'. As you can see, using the bits of
'digits' as a sort of array, indicating which digits we have had so far. So, we have 'digits' = '1010'.

Then, again, n = n / 10 or n = 4.
We shift a '1' again 3 places to the left, getting '1000', and we 'OR' it with digits',
'but since 'digits' already had a '1' in location 4, 'digits' doesn't change:

'1010' OR '1000' = '1010'

and when it detects this, by getting 'digits' = 'digits', the routine knows that it has detected
the same digit more than once, and so n is not a pandigital.

Clever!

But you can achieve the exact same result, by simply using a normal array for this,
and the code will be much easier to follow.

Greetz,
Piet

[Mike. J. Thompson]

And the final step is to produce a binary sequence of 'n' 1's, and compares it to the digit array. If it matches then the number contained the first 'n' digits, and if it doesn't match then it didn't.

[Ranajoy Saha]

Thank You very much! It was of great help from you guys. Thank you for giving a clear understanding how the code is finding out the same recurrent digits Piet Souris and for clearing my misconception about build time being same as the run time Mike J. Thompson! I bet, I'll impress my computer teacher when I use this method to find out the recurring digits!

[Mike. J. Thompson]

Unless you have been taught about bitwise operations then I would hesitate to hand that code in as homework. Your teacher was probably intending to test that you understand about arrays and loops. It will probably be plainly obvious to him or her that you did not produce it yourself.

It reminds me of some homework we were given in a German lesson when I was at school. One girl got her native-German speaking friend to do it for her. The result used words and grammar that we hadn't been taught, so the teacher knew she had had help.

[Campbell Ritchie]

Moving as question too difficult for “beginning”.