Codility ‘FrogRiverOne’ Solution

Short Problem Definition:

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

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.

• 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

• sandip

[Tested 100% correctness, 100% performance]

int solution(int X, vector &A) {
// write your code in C++14 (g++ 6.2.0)
size_t sz = A.size();

if(sz == 0) return -1;
if(X < 1) return -1;
if(sz < (size_t)X-1) return -1;

vector leafOnWay(X,false);

long totalPath = 0;
for(size_t i = 0; i < sz; i++)
{
if(A[i] <= X)
{
if(!leafOnWay[A[i]])
{
leafOnWay[A[i]] = true;
totalPath++;
}
if(totalPath == X)
return i;
}
}

return -1;
}

• Alper Aykac

%100 correctness and %100 performance

public int solution(int X, int[] A) {

int idx = 1, idx2 = 0, max = 0;
int[] tmp = new int[X];
for (int t : A) {
if (t idx) {
tmp[t – 1] = idx;
max = max > idx ? max : idx;
}
}
idx++;
}
if (tmp.length != idx2)
return -1;
else
return max;
}

• Tanuj Sharma

Java 100% / 100%

class Solution {
public int solution(int X, int[] A) {

int retValue = -1;
boolean check[] = new boolean[X+1];
boolean count[] = new boolean[X+1];
boolean missing = false;

for(int i = 0; i < A.length ; i++) {
if(A[i] <= X){
check[A[i]] = true;
}
}

for(int i = 1; i < check.length ; i++) {
if(!check[i]) {
missing = true;
}
}

for(int i= 0; i < A.length ; i++){
if(!missing && A[i] <= X && !count[A[i]] ){
count[A[i]] = true;
retValue = i;
}
}
return retValue;
}
}

• Marcin Gola

Here is my solution in C++( 100 % rank)
using namespace std;
#include

bool checkpath( vector & v )
{
for( size_t i=0 ; i < v.size(); ++i)
{
if( v[i] == -1 )
return false;
}
return true;
}

int solution(int X, vector &A) {

vector path(X,-1);
for( size_t i = 0; i < A.size(); ++i )
{
if( path[A[i] -1 ] == -1 )
path[A[i]-1] = i;
}
if ( !checkpath(path))
return -1;
int max = -1;
for( size_t i = 0; i max )
max = path[i];
}
return max;
}