What is the fastest way to check for duplicate digits of a number?

Question

Let's say I want to check if a number n = 123 has duplicate digits. I tried:

#include <iostream>

using namespace std;

int main() {
    int n = 123;
    int d1 = n % 10;
    int d2 = ( n / 10 ) % 10;
    int d3 = ( n / 100 ) % 10;
    if( d1 != d2 && d1 != d3 && d2 != d3 ) {
        cout << n << " does not have duplicate digits.\n";
    }
}

Is there any faster solution to this problem?

Update
Sorry for being unclear. The code above was written in C++ only for description purpose. I have to solve this problem in TI-89, with a number of 9 digits. And since the limitation of memory and speed, I'm looking for a fastest way possible.

TI-89 only has several condition keyword:

• If
• If ... Then
• when(
• For ... EndFor
• While ... EndWhile
• Loop ... EndLoop
• Custom ... EndCustom

Thanks,
Chan

Answer 1

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

But I believe it's clearer in intent (and simple enough to be translated to a simpler calculator language. It's also able to handle arbitrarily 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 of possibilities, you can use the time-honoured approach of sacrificing space for time. For example, let's say you're talking about numbers between 0 and 999 inclusive (the : : markers simply indicate data I've removed 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 just do a table lookup of hasDupes[n]. The table itself could be generated (once) programmatically and then just inserted into your code for usage.

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

Answer 2

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 as n is nonnegative and int has at least radix bits.

---

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

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

When there are no more digits, return false.

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

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

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