Win a copy of Testing JavaScript Applications this week in the HTML Pages with CSS and JavaScript forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Bear Bibeault
  • Ron McLeod
  • Jeanne Boyarsky
  • Paul Clapham
Sheriffs:
  • Tim Cooke
  • Liutauras Vilda
  • Junilu Lacar
Saloon Keepers:
  • Tim Moores
  • Stephan van Hulst
  • Tim Holloway
  • fred rosenberger
  • salvin francis
Bartenders:
  • Piet Souris
  • Frits Walraven
  • Carey Brown

Pandigital Number (Need understanding of a particular logic)

 
Ranch Hand
Posts: 106
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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



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
 
Bartender
Posts: 689
17
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Bartender
Posts: 4006
156
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Bartender
Posts: 689
17
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Ranch Hand
Posts: 106
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Bartender
Posts: 689
17
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Marshal
Posts: 69864
278
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Moving as question too difficult for “beginning”.
 
In the renaissance, how big were the dinosaurs? Did you have tiny ads?
Thread Boost feature
https://coderanch.com/t/674455/Thread-Boost-feature
    Bookmark Topic Watch Topic
  • New Topic