Can somebody explains what happens in this algorithm to check if its a pandigital?

Question

I know that the << operand shifts the left value of the operand with the value on the right with bits. So 1 << 2 would give 4. And the | operand copies a bit if it exists in either value. But I simply can't get my head around the code.

   private static bool isPandigital(long n)
    {
        int digits = 0;
        int count = 0;
        int tmp;

        while (n > 0)
        {
            tmp = digits;
            digits = digits | 1 << (int)((n % 10) - 1);
            if (tmp == digits)
            {
                return false;
            }

            count++;
            n /= 10;
        }
        return digits == (1 << count) - 1;
    }

Why does it say 1 << in line 8? And why is the module - 1? On top of that I don't know what is happening on the last line when the value is returned. Help would be greatly apreciated. Thanks very much!

How about you run through the application step by step on a seperate piece of paper and a calculator? It's called **analog debugging** and it really helps understanding algorithms sometimes :) — Ian H., Nov 07 '16 at 14:40
I tried debugging with a breakpoint, but yea calculating by hand might be a good idea. I will try it. — Mathijs, Nov 07 '16 at 14:41
Tell me the results; If you still struggle I can give it a try aswell as soon as I come home. — Ian H., Nov 07 '16 at 14:42
Do you mean https://en.wikipedia.org/wiki/Pandigital_number? Do want to test the value with `radix == 10`? — Dmitry Bychenko, Nov 07 '16 at 14:45
I also tested in on a few numbers and it doesn't always give the correct result. At first glance, `(n % 10) - 1` seems wrong, since it can become -1. — Dennis_E, Nov 07 '16 at 14:47
Ok, I think there are several definitions of pandigital. And the algorithm seems to be [here](http://stackoverflow.com/a/2485016/579895) — Pikoh, Nov 07 '16 at 15:03
I think I understand the algorithm :D. Correct me if I am wrong, but what is happening is that you shift the bits to the left and with the | operator you add it to digits. Which means that when you get a number you already had, digits doesnt change. The -1 in line 8 means that you cant have a 0 in your number. On top of that in return you check the amount of itterations. If that is the same (with the -1) as the digits. It's a pandigital. — Mathijs, Nov 07 '16 at 15:07

Scott Chamberlain · Accepted Answer · 2016-11-07T14:50:37.110

Doing

digits = digits | 1 << (int)((n % 10) - 1);

is the same thing as

long temp1 = n % 10; //Divide the number by 10 and get the remainder
long temp2 = temp1 - 1; //Subtract 1 from the remainder.
int temp3 = (int)temp2; //cast the subtracted value to int
int temp4 = 1 << temp3; //left shift 1 to the casted value. This is the same as saying "two to the power of the value of temp3"
int temp5 = digits | temp4; //bitwise or together the values of digits and that leftshifted number.
digits = temp5; //Assign the or'ed value back to digits.

The last line

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

is just doing the same thing as

int temp1 = 1 << count; //left shift 1 `count` times, this is the same as saying "two to the power of the value of count"
int temp2 = temp1 - 1; //Subtract 1 from the leftshifted number.
bool temp3 = digits == temp2; //test to see if digits equals temp2
return temp3;

I don't know what "pandigital" means, but this break apart can help you understand what is happening.

[a pandigital number is an integer that in a given base has among its significant digits each digit used in the base at least once](https://en.wikipedia.org/wiki/Pandigital_number) I didn't know either but seems intresting — M.kazem Akhgary, Nov 07 '16 at 14:49

Dmitry Bychenko · Answer 2 · 2016-11-07T14:59:53.657

If pandigital means "contains all possible digits for the given radix"

https://en.wikipedia.org/wiki/Pandigital_number

and the radix == 10, why not just check if the number contains all possible 0..9 digits:

private static bool isPandigital(long n) {
  // I assume negative numbers cannot be pandigital;
  // if they can, put n = Math.Abs(n);  
  if (n < 1023456789) // smallest pandigital
    return false;

  int[] digits = new int[10];

  for (; n > 0; n /= 10) 
    digits[n % 10] += 1;

  return digits.All(item => item > 0);
}

Edit: In case of bit array (each bit in digits represent a digit) implementation:

private static bool isPandigital(long n) {
  // negative numbers can't be pandigital 
  if (n < 1023456789) // smallest pandigital
    return false;

  int digits = 0;

  for (; n > 0; n /= 10) 
    digits |= (1 << (int)(n % 10));

  // 0b1111111111
  return digits == 1023;
}

That is exactly what the function is trying to do. Of course, it uses a bit array to record what digits have been used, instead of the int[] you use. And it has bugs, which is probably why OP doesn't understand it. — Kris Vandermotten, Nov 07 '16 at 14:56
This doesn't attempt to answer the question. It asks for an explanation of the algorithm, not a code dump. — Esoteric Screen Name, Nov 07 '16 at 15:02

Dennis_E · Answer 3 · 2016-11-07T15:24:33.097

I think the writer of the method attempted to do this:

static bool IsPandigital(long n) {
    int digits = 0;
    while (n > 0) {
        //set the bit corresponding to the last digit of n to 1 (true)
        digits |= 1 << (int)(n % 10);
        //remove the last digit of n
        n /= 10;
    }
    //digits must be equal to 1111111111 (in binary)
    return digits == (1 << 10) - 1;
 }

The << operator is not that difficult. You just have to think in binary.

1 << 0 is simply a 1 shifted zero places, so 1
1 << 1 is 10
1 << 2 is 100, etc
If you encounter a 2 and a 5 and you 'or' them together you will have 100100.
This means if you encounter all 10 digits, the end result will be ten 1's.

In the return statement, we check if digits equals ten 1's.
1 << 10 means a 10000000000. If you substract 1, you get 1111111111
All this in binary, of course.

He may have had a different definition of pandigital, or just a different requirement. If, for example zeroes are not allowed, you can simply change the last line to: digits == (1 << 10) - 2;

This doesn't attempt to answer the question. It asks for an explanation of the algorithm, not a code dump. — Esoteric Screen Name, Nov 07 '16 at 15:03

Can somebody explains what happens in this algorithm to check if its a pandigital?

3 Answers3