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

Accepted answer
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) {
    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.

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