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

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.

```
template<class T, int radix = 10>
bool has_duplicate_digits(T n) {
int digits_mask = 0;
while (digits_mask |= (1 << (n % radix)), n /= radix)
if (digits_mask & (1 << (n % radix)))
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.

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

We use cookies to improve the performance of the site. By staying on our site, you agree to the terms of use of cookies.