Какой самый быстрый способ проверить наличие повторяющихся цифр числа?

Question

Допустим, я хочу проверить, имеет ли число n = 123 повторяющиеся цифры. Я попробовал:

#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";
    }
}

Есть ли более быстрое решение этой проблемы?

Обновление
Извините за то, что неясно. Код выше был написан на C ++ только для целей описания. Я должен решить эту проблему в TI-89, с числом 9 цифр. А так как ограничение памяти и скорости я ищу как можно быстрее.

TI-89 имеет только несколько ключевых слов условия:

• Если
• Если ... Тогда
• когда (
• Для ... EndFor
• Пока ... EndWhile
• Loop ... EndLoop
• Custom ... EndCustom

Спасибо
Чан

Answer 1

Быстрее, возможно, нет (но вы должны все равно измерить, на всякий случай - моя мантра оптимизации - "measure, don't guess"). Но я думаю, что яснее в намерениях, и способен обрабатывать целые числа произвольного размера.

int hasDupes (unsigned int n) {
    // Flag to indicate digit has been used.

    int i, used[10];

    // Must have dupes if more than ten digits.

    if (n > 9999999999)
        return 1;

    // Initialise dupe flags to false.

    for (i = 0; i < 10; i++)
        used[i] = 0;

    // Process all digits in number.

    while (n != 0) {
        // Already used? Return true.

        if (used[n%10])  // you can cache n%10 if compiler not too smart.
            return 1;

        // Otherwise, mark used, go to next digit.

        used[n%10] = 1;  // and you would use cached value here.
        n /= 10;
    }

    // No dupes, return false.

    return 0;
}

---

Если у вас ограниченный диапазон возможностей, вы можете использовать проверенный временем подход, заключающийся в том, чтобы жертвовать пространством ради времени.

Допустим, вы говорите о числах от 0 до 999:

const int *hasDupes = {
//  0  1  2  3  4  5  6  7  8  9
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0,  //   x
    0, 1, 0, 0, 0, 0, 0, 0, 0, 0,  //  1x
    0, 0, 1, 0, 0, 0, 0, 0, 0, 0,  //  2x
    :
    0, 0, 0, 0, 0, 0, 0, 1, 0, 1,  // 97x
    0, 0, 0, 0, 0, 0, 0, 0, 1, 1,  // 98x
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1,  // 99x
};

и просто выполните поиск по таблице hasDupes[n].

---

Исходя из ваших правок, когда вам нужно обработать девять цифр, массив из миллиарда элементов (второе решение выше), вероятно, будет невозможен для вашего калькулятора: -)

Я бы выбрал первое решение.

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;
}

Что-то подобное должно работать, если n неотрицательно и int имеет по крайней мере radix бит.

---

digits_mask - это битовый набор (бит 0 представляетвхождение цифры 0, бит 1 представляет вхождение цифры 1 и т. д.).

Растровое изображение заполняется младшей значащей цифрой n, а остальные цифры сдвигаются вниз,Если цифр больше, а новая младшая цифра помечена как появившаяся ранее, верните true, в противном случае повторите.

Если цифр больше нет, верните false.

1 << xвозвращает 1, 2, 4, 8 и т. д .: маски, используемые для проверки / установки битов в наборе битов.

a |= z является сокращением для a = a | z, которое устанавливает биты путем объединения aот z.

a & z - пересечение битов в a и z, и оно равно нулю (false), если ни один не установлен, и ненулевым (true), если они установлены.

Answer 3

Я прошел ускоренный курс по основному TI-89, чтобы ответить :)

Давайте посмотрим, работает ли это (у меня нет эмулятора, поэтому не могу проверить).

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