¿Cuál es la manera más rápida de verificar si hay dígitos duplicados de un número?

Question

Digamos que quiero verificar si un número n = 123 tiene dígitos duplicados. Intenté:

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

¿Hay alguna solución más rápida a este problema?

Actualización
Disculpe por no estar clara. El código anterior se escribió en C++ solo con fines descriptivos. Tengo que resolver este problema en TI-89, con un número de 9 dígitos. Y dado que la limitación de la memoria y la velocidad, estoy buscando la forma más rápida posible.

TI-89 tiene varias condiciones palabra clave:

• Si
• Si ... Entonces
• cuando (
• Para EndFor ...
• tiempo ... EndWhile
• Loop ... EndLoop
• Personalizado ... EndCustom

Gracias,
Chan

Answer 1

más rápido, posiblemente no (pero usted debe medir todos modos, por si acaso - mi optimización mantra es "measure, don't guess"). Pero más clara en su intención, creo, sí, y es capaz de manejar enteros de tamaño arbitrario.

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

---

Si usted tiene un número limitado de posibilidades, puede utilizar el enfoque de larga tradición de sacrificar espacio de tiempo.

decir que estás hablando de números entre 0 y 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 
}; 

y sólo hacer una búsqueda en la tabla de hasDupes[n].

---

Basado en su edición cuando se necesita para manejar nueve dígitos, una matriz de mil millones de elementos (segunda solución anterior) probablemente no va a ser posible en su calculadora :-)

optaría por la primera solució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; 
} 

Algo así debería funcionar siempre y cuando n es no negativo y int tiene al menos radix bits.

---

digits_mask es una bitset (bit 0 representa la ocurrencia de un 0 dígito, bit 1 representa la ocurrencia de un 1 dígito, etc.).

El mapa de bits se rellena con el dígito menos significativo de n, y el resto de los dígitos se desplazan hacia abajo.Si hay más dígitos, y el nuevo dígito menos significativo está marcado como que ocurrió anteriormente, devuelva verdadero, de lo contrario, repita.

Cuando no hay más dígitos, devuelve falso.

1 << x devuelve 1, 2, 4, 8, etc .: máscaras para usar para probar/establecer bits en el conjunto de bits.

a |= z es la abreviatura de a = a | z, que establece los bits por la unión de a de z.

a & z es la intersección de los bits en a y z, y es cero (falso) si ninguno se introducen y no cero (verdadero) si cualquier están ajustadas.

Answer 3

lo hice un curso intensivo de TI-89 básico para responder :)

Vamos a ver si esto funciona (yo no tengo un emulador, por lo que no se puede comprobar).

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