tiene - sumar los digitos de un numero en c++

Encuentre eficientemente un número entero que no esté en un conjunto de tamaño 40, 400 o 4000

Question

En relación con el problema clásico, encuentre un número entero no entre los cuatro mil millones dados, pero no exactamente el mismo.

Para aclarar, por enteros lo que realmente quiero decir es solo un subconjunto de su definición matemática. Es decir, supongamos que solo hay un número finito de enteros. Digamos que en C ++, están en el rango de [INT_MIN, INT_MAX] .

Ahora se le da un std::vector<int> (sin duplicados) o std::unordered_set<int> , cuyo tamaño puede ser 40, 400, 4000 o algo así, pero no demasiado grande, cómo generar un número de manera eficiente que garantice no estar entre los dados?

Si no hay preocupación por el desbordamiento, entonces podría multiplicar todos los no distintos a cero y agregar el producto por 1. Pero hay. Los casos de prueba del adversario podrían contener de forma INT_MAX .

Estoy más a favor de los enfoques simples y no aleatorios. ¿Hay alguna?

¡Gracias!

Actualización: para aclarar la ambigüedad, digamos un std::vector<int> sin clasificar que se garantiza que no tiene duplicados. Así que estoy preguntando si hay algo mejor que O (n log (n)). También tenga en cuenta que los casos de prueba pueden contener tanto INT_MIN como INT_MAX .

Answer 1

Haz aleatorio x (INT_MIN..INT_MAX) y pruébalo contra todos. Prueba x ++ en caso de fallo (caso muy raro para 40/400/4000).

Answer 2

Los métodos aleatorios son ciertamente muy eficientes aquí.

Si queremos usar un método determinista y asumiendo que el tamaño n no es demasiado grande, 4000 por ejemplo, entonces podemos crear un vector x de tamaño m = n + 1 (o un poco más grande, 4096 por ejemplo para facilitar el cálculo ), inicializado con 0.

Para cada i en el rango, simplemente establecemos x [array [i] modulo m] = 1.

Entonces, una simple búsqueda O (n) en x proporcionará un valor que no está en la matriz

Nota: la operación de módulo no es exactamente la operación "%"

Edición: mencioné que los cálculos se hacen más fáciles seleccionando aquí un tamaño de 4096. Para ser más concretos, esto implica que la operación de módulo se realiza con un simple & operación

Answer 3

Para el caso en el que los enteros se proporcionan en un std::unordered_set<int> (a diferencia de un std::vector<int> ), simplemente podría atravesar el rango de valores enteros hasta que encuentre un valor entero que no está presente en unordered_set<int> . La búsqueda de la presencia de un número entero en un std::unordered_set<int> es bastante sencilla, ya que std::unodered_set proporciona una búsqueda a través de su función de miembro find() .

La complejidad espacial de este enfoque sería O (1) .

Si comienza a atravesar en el valor más bajo posible para un int (es decir, std::numeric_limits<int>::min() ), obtendrá el int más bajo no contenido en el std::unordered_set<int> :

int find_lowest_not_contained(const std::unordered_set<int>& set) {
   for (auto i = std::numeric_limits<int>::min(); ; ++i) {
      auto it = set.find(i); // search in set
      if (it == set.end()) // integer not in set?
         return *it;
   }
}

Análogamente, si comienza a recorrer el mayor valor posible para un int (es decir, std::numeric_limits<int>::max() ), obtendrá el int más bajo no contenido en std::unordered_set<int> :

int find_greatest_not_contained(const std::unordered_set<int>& set) {
   for (auto i = std::numeric_limits<int>::max(); ; --i) {
      auto it = set.find(i); // search in set
      if (it == set.end()) // integer not in set?
         return *it;
   }
}

Suponiendo que los int s están asignados de manera uniforme por la función hash en los unordered_set<int> unordered_set<int> se puede lograr una operación de búsqueda en unordered_set<int> en tiempo constante. La complejidad del tiempo de ejecución sería entonces O (M) , donde M es el tamaño del rango entero que busca un valor no contenido. M está limitado por el tamaño de unordered_set<int> (es decir, en su caso M <= 4000 ).

De hecho, con este enfoque, se garantiza que la selección de cualquier rango de enteros cuyo tamaño sea mayor que el tamaño de unordered_set , unordered_set un valor entero que no está presente en unordered_set<int> .

Answer 4

Puede encontrar el número entero no utilizado más pequeño en tiempo O (N) usando el espacio auxiliar O (1) si se le permite reordenar el vector de entrada, usando el siguiente algoritmo. [Nota 1] (El algoritmo también funciona si el vector contiene datos repetidos.)

size_t smallest_unused(std::vector<unsigned>& data) {
  size_t N = data.size(), scan = 0;
  while (scan < N) {
    auto other = data[scan];
    if (other < scan && data[other] != other) {
      data[scan] = data[other];
      data[other] = other;
    }
    else
      ++scan;
  }
  for (scan = 0; scan < N && data[scan] == scan; ++scan) { }
  return scan;
}

La primera pasada garantiza que si se encontró algo de k en el rango [0, N) después de la posición k , entonces ahora está presente en la posición k . Esta reorganización se realiza mediante el intercambio para evitar la pérdida de datos. Una vez que se completa esa exploración, la primera entrada cuyo valor no es el mismo que su índice no se hace referencia en ninguna parte de la matriz.

Es posible que esa afirmación no sea 100% obvia, ya que se podría hacer referencia a una entrada de un índice anterior. Sin embargo, en ese caso, la entrada no podría ser la primera entrada desigual a su índice, ya que la entrada anterior cumpliría con ese criterio.

Para ver que este algoritmo es O (N), debe observarse que el intercambio en las líneas 6 y 7 solo puede ocurrir si la entrada objetivo no es igual a su índice, y que después del intercambio la entrada objetivo es igual a su índice . Por lo tanto, en la mayoría de los casos, se pueden realizar N swaps, y la condición if en la línea 5 se cumplirá como máximo N veces. Por otro lado, si la condición if es falsa, el scan se incrementará, lo que también puede ocurrir N veces. Por lo tanto, la instrucción if se evalúa como máximo 2N veces (que es O (N)).

Notas:

1. Utilicé enteros sin signo aquí porque hace que el código sea más claro. El algoritmo puede ajustarse fácilmente para los enteros con signo, por ejemplo, mediante la asignación de enteros con signo de [INT_MIN, 0) sobre enteros sin signo [INT_MAX, INT_MAX - INT_MIN) (La resta es matemática, no de acuerdo con la semántica C que no permitiría el resultado para ser representado.) En el complemento de 2, ese es el mismo patrón de bits. Eso cambia el orden de los números, por supuesto, lo que afecta la semántica del "entero más pequeño no utilizado"; También se podría utilizar un mapeo para preservar el orden.

Answer 5

Simplemente podría devolver el primero de los N+1 enteros candidatos que no se encuentran en su entrada. Los candidatos más simples son los números 0 a N Esto requiere O(N) espacio y tiempo.

 int find_not_contained(container<int> const&data)
 {
     const int N=data.size();
     std::vector<char> known(N+1, 0);   // one more candidates than data
     for(int i=0; i< N; ++i)
         if(data[i]>=0 && data[i]<=N)
             known[data[i]]=1;
     for(int i=0; i<=N; ++i)
         if(!known[i])
             return i;
     assert(false);                     // should never be reached.
 }

Los métodos aleatorios pueden ser más eficientes en el espacio, pero pueden requerir más pases sobre los datos en el peor de los casos.

Answer 6

Paso 1: Ordenar el vector .

Esto se puede hacer en O (n log (n)), puede encontrar algunos algoritmos diferentes en línea, use el que más le guste.

Paso 2: Encuentra el primer int no en el vector .

Fácilmente iterar desde INT_MIN a INT_MIN + 40/400/4000 comprobando si el vector tiene el int actual:

Pseudocódigo

SIZE = 40|400|4000 // The one you are using
for (int i = 0; i < SIZE; i++) {
    if (array[i] != INT_MIN + i)
        return INT_MIN + i;

La solución sería O (n log (n) + n) significado: O (n log (n))

Editar: solo lea su edición pidiendo algo mejor que O (n log (n)) , lo siento.