[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.