es.davy.ai

Preguntas y respuestas de programación confiables

¿Tienes una pregunta?

Si tienes alguna pregunta, puedes hacerla a continuación o ingresar lo que estás buscando.

Tarea de prueba en C – aparentemente mi solución no supera algunos casos de prueba.

06 Aug, 2023 Programación

Actualmente estoy tratando de practicar mis habilidades en C en algunas tareas de prueba de demostración. Me encontré con la siguiente tarea e implementé una solución que no pasa la prueba. ¿Puedes revisar mi solución y señalar qué casos he pasado por alto alternativamente cómo podría hacer la solución más eficiente? ¡Básicamente cualquier entrada es apreciada!

Tarea:

Escribe una función:

int solution(int A[], int N);

que, dado un array A de N enteros, devuelve el entero positivo más pequeño (mayor que 0) que no aparece en A. Por ejemplo, dado A = [1, 3, 6, 4, 1, 2], la función debería devolver 5. Dado A = [1, 2, 3], la función debería devolver 4. Dado A = [-1, -3], la función debería devolver 1.

Escribe un algoritmo eficiente para las siguientes suposiciones: N es un entero dentro del rango [1..100,000]; cada elemento del array A es un entero dentro del rango [-1,000,000..1,000,000].

Mi solución:

int solution(int A[], int N) {
 int B[N];
    unsigned int Bidx=0;
    unsigned int i = 0;
    int smallest = 1000000;

    // deshacerse de los elementos negativos y encontrar el elemento positivo más pequeño
    for(i=0; i<;N; i++)
    {
        if(A[i]>0)
        {
            B[Bidx]=A[i];
            Bidx++;
            if(A[i] < smallest)
                smallest = A[i];
        }
    }

    // si no se encuentran elementos positivos, la solución es 1
    if(Bidx == 0)
        return 1;

    // iterar a través de los valores positivos para encontrar el valor no presente más pequeño
    int condition = 1;
    int candidate = smallest+1;

    while(condition)
    {
        condition = 0;

        for(i=0; i < Bidx; i++)
        {
            if(B[i] == candidate)
            {
                candidate++;
                condition = 1;
            }
        }
    }    

    return candidate;
}
Tags:  

Answer

  1. Avatar for davy.ai
    davy.ai

    Tu solución es correcta para la mayoría de los casos, pero hay algunos casos extremos que tu solución no cubre, que son los siguientes:

    • Cuando el entero positivo más pequeño en el array es mayor a 1, tu solución retornará 1 en lugar del siguiente entero positivo más pequeño.
    • Cuando el array contiene duplicados de enteros positivos, tu solución los omitirá y no los considerará.

    Para solucionar estos problemas, puedes modificar tu solución de la siguiente manera:

    • Después de eliminar los elementos negativos, verifica si el elemento positivo más pequeño es mayor a 1. Si es así, retorna 1.
    • Ordena el array de elementos positivos en orden ascendente y luego itera a través de él para encontrar el valor faltante más pequeño.

    Aquí tienes el código actualizado:

    int solution(int A[], int N) {
    int B[N];
    unsigned int Bidx = 0;

    // eliminar elementos negativos
    for (unsigned int i = 0; i < N; i++) {
        if (A[i] > 0) {
            B[Bidx] = A[i];
            Bidx++;
        }
    }

    // verificar si el entero positivo más pequeño es mayor a 1
    if (Bidx == 0 || B[0] > 1) {
        return 1;
    }

    // ordenar el array de elementos positivos
    qsort(B, Bidx, sizeof(int), cmpfunc);

    // encontrar el valor faltante más pequeño
    int smallest = 1;
    for (unsigned int i = 0; i < Bidx; i++) {
        if (B[i] == smallest) {
            smallest++;
        } else if (B[i] > smallest) {
            return smallest;
        }
    }

    return smallest;
}

// función de comparación para qsort
int cmpfunc(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}

    Esta solución debería ser más eficiente y cubrir todos los casos extremos.

Comments are closed.