Problema:

A small frog wants to get to the other side of a river. The frog is currently located at position 0, and wants to get to position X. Leaves fall from a tree onto the surface of the river.

You are given a non-empty zero-indexed array A consisting of N integers representing the falling leaves. A[K] represents the position where one leaf falls at time K, measured in seconds.

The goal is to find the earliest time when the frog can jump to the other side of the river. The frog can cross only when leaves appear at every position across the river from 1 to X. You may assume that the speed of the current in the river is negligibly small, i.e. the leaves do not change their positions once they fall in the river.

For example, you are given integer X = 5 and array A such that:

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

In second 6, a leaf falls into position 5. This is the earliest time when leaves appear in every position across the river.

Write a function:

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

that, given a non-empty zero-indexed array A consisting of N integers and integer X, returns the earliest time when the frog can jump to the other side of the river.

If the frog is never able to jump to the other side of the river, the function should return −1.

For example, given X = 5 and array A such that:

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

the function should return 6, as explained above.

Assume that:

  • N and X are integers within the range [1..100,000];
  • each element of array A is an integer within the range [1..X].

Complexity:

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

Elements of input arrays can be modified.

Solución:


def solution(X, A):
    leafs = [0] * X
    clear = X
    for x in xrange(0, len(A)):
        if leafs[A[x]-1] == 0:
            leafs[A[x]-1] = 1
            clear -= 1
        if clear == 0:
            return x
    return -1

Este problema me costo un poco entenderlo, pero nos dice que hay una ranita que quiere saltar al otro lado del rió, la ranita esta en la posición 0 y quiere ir a la posición X. dado un array A, representa el rió y A[K] representa la posición donde cayo la hoja en el segundo K. Por ejemplo:

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

Esto nos dice que en el segundo 0 cayo una hoja en la posición 1 y en el segundo 1 callo una hoja en la posición 3 y en el segundo 2 callo otra vez en la posición uno y así sucesivamente. La ranita quiere llegar a X por lo tanto la ranita no podrá pasar hasta que haya caído una hoja en la posición 5 y eso sucederá hasta el segundo 6 siempre y cuando todo su camino este lleno de hojas, por lo tanto si en el primer segundo cae la hoja en la posición 5 no significa que la ranita podrá cruzar en el segundo 1, si no hasta que todo el camino hasta 5 este lleno de hojas. En mi solución hago lo siguiente:

  • Creo una lista llena de 0’s del tamaño de X
  • Creo un contador para saber cuando todo el camino este lleno de hojas
  • Después itero y voy poniendo 1 en todas las posiciones done ya haya hojas.

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

It's only fair to share...Share on Facebook2Tweet about this on TwitterShare on Google+1Share 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.