Problema:

Write a function:

def solution(A)

that, given a non-empty zero-indexed array A of N integers, returns the minimal positive integer (greater than 0) that does not occur in A.

For example, given:

A[0] = 1 A[1] = 3 A[2] = 6 A[3] = 4 A[4] = 1 A[5] = 2

the function should return 5.

Assume that:

  • N is an integer within the range [1..100,000];
  • each element of array A is an integer within the range [−2,147,483,648..2,147,483,647].

Complexity:

  • expected worst-case time complexity is O(N);
  • expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).

Elements of input arrays can be modified.

Solución:


def solution(A):
    size = len(A) + 1
    seen = [False] * size
    for x in A:
        if x > 0 and x < size:
            seen[x-1] = True
    return seen.index(False) + 1

El problema nos dice que dado un array de N números retornemos el numero positivo mas chico mayor que cero que no se encuentre en la lista por ejemplo:

A = [1, 2, 3, 5, 6]

Esto nos retornaría 4, por que es el menor numero posible.

Lo que hago es crear un array de números “vistos” con la misma cantidad de elementos que A mas uno (A+1), después itero sobre los elementos de A y uso los indices de “seen” como los números y los marco como vistos, al final solo busco cual indice esta en falso y ese es el numero mas chico posible mayor a cero.

Aquí esta el repo con todas mis soluciones de codility: https://github.com/OmarIbannez/codility-lessons

It's only fair to share...Share on Facebook1Tweet about this on TwitterShare on Google+0Share on LinkedIn0Share on Reddit0Pin on Pinterest0Email this to someone

Leave a Reply

Your email address will not be published. Required fields are marked *

Comment moderation is enabled. Your comment may take some time to appear.