Codility ‘FrogRiverOne’ Solution

Short Problem Definition:

Find the earliest time when a frog can jump to the other side of a river.

Link

FrogRiverOne

Complexity:

expected worst-case time complexity is O(N);

expected worst-case space complexity is O(X)

Execution:

Mark seen elements as such in a boolean array. I do not like the idea of returning the first second as 0. But specifications are specifications 🙂

Solution:
def solution(X, A):
    passable = [False] * X
    uncovered = X

    for idx in xrange(len(A)):
        if A[idx] <= 0 or A[idx] > X:
            raise Exception("Invalid value", A[idx])
        if passable[A[idx]-1] == False:
            passable[A[idx]-1] = True
            uncovered -= 1
            if uncovered == 0:
                return idx

    return -1

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

Facebooktwittergoogle_plusredditpinterestlinkedin
  • Guest

    int solution(int X, vector &A) {
    vector seen(A.size(),false);
    int tot = 0;//When reach X the frog has all the leaves

    for(unsigned int i=0; i<A.size(); i++){
    if( A[i] <= X && (seen[A[i]-1] == false) ){
    seen[A[i]-1] = true;
    tot++;
    if (tot == X){
    return i;
    }
    }
    }

    return -1;
    }

  • Hey,

    I reformated your C++ code, to be properly displayed by Disqus. It ranks as 100/100 :). Nice

  • Nehemiah Jacob

    This scored 100%, Bit scary that I didn’t check boundaries, Yet it was through. Choosing ‘Set’ was a good choice here that can store leaf positions uniquely

    def solution(X, A):
    s = set()
    for i in xrange(len(A)):
    if A[i] <= X: #Add leaf position if matters
    s.add(A[i])
    if len(s) == X: #By this time s = {5,4,3,2,1,0}
    return i
    return -1

  • Yeah, most of the code you write for codility would not live for long in production :). Anyways, I like your solution more than mine. I did not use it though, because set insertion has log(N) complexity in C++. Therefore your overall runtime would be N*log(N) and not the expected N 🙂

    You can even kick the X check to get 100/100 🙂


    def solution(X, A):
    s = set()
    for i in xrange(len(A)):
    s.add(A[i])
    if len(s) == X: #By this time s = {5,4,3,2,1,0}
    return i

    return -1

  • Yogendra

    C# Solution : 100%

    class Solution {
    public int solution(int x, int[] _LeafPosition) {
    // write your code in C# 6.0 with .NET 4.5 (Mono)

    int _index = Array.FindIndex(_LeafPosition, r => r.Equals(x));

    if (_index >= 0)
    {
    var _missing = Enumerable.Range(1, x).ToList();
    if (_missing.Count > 0)
    {

    var _missingIndex = _LeafPosition.Intersect(_missing).ToList();
    if (_missingIndex.Count == x)
    {
    _index = Array.FindIndex(_LeafPosition, r => r.Equals(_missingIndex.Last()));
    }
    else
    {
    _index = -1;
    }

    }
    }
    else
    {
    _index = -1;
    }

    return _index;

    }
    }

  • Kamil Gregorczyk

    I wanted to by fast and got 18% with “return A.index(X) if X in A else -1” :/ don’t try this at home