# [ACCEPTED]-What is the fastest way to check for duplicate digits of a number?-numbers

Score: 11

Not necessarily faster but you should measure anyway, just 19 in case - my optimisation mantra is `"measure, don't guess"`.

But 18 I believe it's clearer in intent (and simple 17 enough to be translated to a simpler calculator 16 language. It's also able to handle arbitrarily 15 sized integers.

``````int hasDupes (unsigned int n) {
// Flag to indicate digit has been used, all zero to start.
int used[10] = {0};

// More than 10 digits must have duplicates, return true quickly.
if (n > 9999999999) return 1;

// Process each digit in number.
while (n != 0) {
// If duplicate, return true as soon as found.
if (used[n%10]) return 1;

// Otherwise, mark used, go to next digit.
used[n%10] = 1;
n /= 10;
}

// No duplicates after checking all digits, return false.
return 0;
}
``````

If you have a limited range 14 of possibilities, you can use the time-honoured 13 approach of sacrificing space for time. For 12 example, let's say you're talking about 11 numbers between 0 and 999 inclusive (the 10 `: :` markers simply indicate data I've removed 9 to keep the size of the answer manageable):

``````const int *hasDupes = {
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,  //   0 -   9
0, 1, 0, 0, 0, 0, 0, 0, 0, 0,  //  10 -  19
0, 0, 1, 0, 0, 0, 0, 0, 0, 0,  //  20 -  29
:  :
0, 0, 1, 0, 0, 1, 0, 0, 0, 0,  // 520 - 529
:  :
0, 1, 0, 0, 0, 0, 0, 0, 1, 0,  // 810 - 819
:  :
0, 0, 0, 0, 0, 0, 0, 1, 0, 1,  // 970 - 979
0, 0, 0, 0, 0, 0, 0, 0, 1, 1,  // 980 - 989
1, 1, 1, 1, 1, 1, 1, 1, 1, 1,  // 990 - 999
};
``````

and 8 just do a table lookup of `hasDupes[n]`. The table itself 7 could be generated (once) programmatically 6 and then just inserted into your code for 5 usage.

However, based on your edit where 4 you state you need to handle nine-digit 3 numbers, a billion-element array is probably 2 not going to be possible on your calculator. I 1 would therefore opt for the first solution.

Score: 3
``````template<class T, int radix = 10>
bool has_duplicate_digits(T n) {
return true;
return false;
}
``````

Something like that should work as long 16 as `n` is nonnegative and `int` has at least `radix` bits.

`digits_mask` is 15 a bitset (bit 0 represents the occurrence 14 of a 0 digit, bit 1 represents the occurrence 13 of a 1 digit, etc.).

The bitmap is populated 12 with the least significant digit of `n`, and 11 the rest of the digits are shifted down. If 10 there are more digits, and the new least 9 significant digit is marked as having occurred 8 previously, return true, otherwise repeat.

When 7 there are no more digits, return false.

`1 << x` returns 6 1, 2, 4, 8, etc.: masks to use to test/set 5 bits in the bitset.

`a |= z` is shorthand for `a = a | z`, which 4 sets bits by the union of `a` from `z`.

`a & z` is the 3 intersection of the bits in `a` and `z`, and is 2 zero (false) if none are set and non-zero 1 (true) if any are set.

Score: 1

I did a crash course in TI-89 basic to answer 2 :)

Let's see if this works (I haven't an 1 emulator, so can't check).

``````Test()
Prgm
{0,0,0,0,0,0,0,0,0,0}->A
Title "Request"
Request "Enter a number",B
EndDlog
Expr(B)->B
While  B > 1
MOD(10,B)->C
if A[C+1] = 1 goto K
1->A[C+1]
B-C->B
EndWhile
Title "Done"
Text "Numbers non repeating"
Enddlog
goto J

Lbl K
Title "Done"
Text "Numbers repeating"
Enddlog

Lbl J
EndPrgm
``````

More Related questions