Tasks Details
easy
1.
FrogRiverOne
Find the earliest time when a frog can jump to the other side of a river.
Task Score
63%
Correctness
100%
Performance
20%
A small frog wants to get to the other side of a river. The frog is initially located on one bank of the river (position 0) and wants to get to the opposite bank (position X+1). Leaves fall from a tree onto the surface of the river.
You are given an 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 (that is, we want to find the earliest moment when all the positions from 1 to X are covered by leaves). 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] = 4In 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:
class Solution { public int solution(int X, int[] A); }
that, given a non-empty 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] = 4the function should return 6, as explained above.
Write an efficient algorithm for the following assumptions:
- N and X are integers within the range [1..100,000];
- each element of array A is an integer within the range [1..X].
Copyright 2009–2025 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
Solution
Programming language used C#
Time spent on task 77 minutes
Notes
not defined yet
Code: 07:13:26 UTC,
cs,
verify,
result: Failed
using System;
// you can also use other imports, for example:
// using System.Collections.Generic;
// you can write to stdout for debugging purposes, e.g.
// Console.WriteLine("this is a debug message");
class Solution {
public int solution(int X, int[] A) {
// write your code in C# 6.0 with .NET 4.5 (Mono)
}
}
Analysis
Compile error
Compilation failed: 1 error(s), 0 warnings Solution.cs(9,16): error CS0161: `Solution.solution(int, int[])': not all code paths return a value
Code: 07:13:53 UTC,
cs,
verify,
result: Passed
using System;
// you can also use other imports, for example:
// using System.Collections.Generic;
// you can write to stdout for debugging purposes, e.g.
// Console.WriteLine("this is a debug message");
class Solution {
public int solution(int X, int[] A) {
// write your code in C# 6.0 with .NET 4.5 (Mono)
for(int i = 0; i < A.Length; i++)
{
if(A[i] == X)
{
return i;
}
}
return -1;
}
}
User test case 1:
[2, [1, 2, 3, 4, 5, 6, 7]]
Analysis
Code: 07:14:16 UTC,
cs,
verify,
result: Passed
using System;
// you can also use other imports, for example:
// using System.Collections.Generic;
// you can write to stdout for debugging purposes, e.g.
// Console.WriteLine("this is a debug message");
class Solution {
public int solution(int X, int[] A) {
// write your code in C# 6.0 with .NET 4.5 (Mono)
for(int i = 0; i < A.Length; i++)
{
if(A[i] == X)
{
return i;
}
}
return -1;
}
}
User test case 1:
[2, [7, 6, 5, 4, 3, 2, 1]]
Analysis
Code: 08:19:23 UTC,
cs,
verify,
result: Failed
using System;
class Solution {
public int solution(int X, int[] A) {
List<bool> checkList = new List<bool>();
for(int i = 0; i < X; i++)
{
checkList.Add(false);
}
for(int i = 0; i < A.Length; i++)
{
if(A[i] <= X)
{
checkList[A[i]] = true;
}
bool allTrue = true;
for(int i = 0; i < checkList.Count; i++)
{
if(checkList[i] == false) allTrue = false;
}
if(allTrue) return i;
}
// couldn't get to the other side of the river.
return -1;
}
}
Analysis
Compile error
Compilation failed: 1 error(s), 0 warnings Solution.cs(22,21): error CS0136: A local variable named `i' cannot be declared in this scope because it would give a different meaning to `i', which is already used in a `parent or current' scope to denote something else
Code: 08:19:52 UTC,
cs,
verify,
result: Failed
using System;
class Solution {
public int solution(int X, int[] A) {
List<bool> checkList = new List<bool>();
for(int i = 0; i < X; i++)
{
checkList.Add(false);
}
for(int i = 0; i < A.Length; i++)
{
if(A[i] <= X)
{
checkList[A[i]] = true;
}
bool allTrue = true;
for(int j = 0; j < checkList.Count; j++)
{
if(checkList[j] == false) allTrue = false;
}
if(allTrue) return i;
}
// couldn't get to the other side of the river.
return -1;
}
}
Analysis
Compile error
Compilation failed: 5 error(s), 0 warnings Solution.cs(6,9): error CS0246: The type or namespace name `List' could not be found. Are you missing `System.Collections.Generic' using directive? Solution.cs(10,13): error CS0841: A local variable `checkList' cannot be used before it is declared Solution.cs(17,17): error CS0841: A local variable `checkList' cannot be used before it is declared Solution.cs(22,32): error CS0841: A local variable `checkList' cannot be used before it is declared Solution.cs(24,20): error CS0841: A local variable `checkList' cannot be used before it is declared
Code: 08:20:29 UTC,
cs,
verify,
result: Failed
using System;
using System.Collection.Generics;
class Solution {
public int solution(int X, int[] A) {
List<bool> checkList = new List<bool>();
for(int i = 0; i < X; i++)
{
checkList.Add(false);
}
for(int i = 0; i < A.Length; i++)
{
if(A[i] <= X)
{
checkList[A[i]] = true;
}
bool allTrue = true;
for(int j = 0; j < checkList.Count; j++)
{
if(checkList[j] == false) allTrue = false;
}
if(allTrue) return i;
}
// couldn't get to the other side of the river.
return -1;
}
}
Analysis
Compile error
Compilation failed: 1 error(s), 0 warnings Solution.cs(2,14): error CS0234: The type or namespace name `Collection' does not exist in the namespace `System'. Are you missing an assembly reference?
Code: 08:20:48 UTC,
cs,
verify,
result: Failed
using System;
using System.Collections.Generic;
class Solution {
public int solution(int X, int[] A) {
List<bool> checkList = new List<bool>();
for(int i = 0; i < X; i++)
{
checkList.Add(false);
}
for(int i = 0; i < A.Length; i++)
{
if(A[i] <= X)
{
checkList[A[i]] = true;
}
bool allTrue = true;
for(int j = 0; j < checkList.Count; j++)
{
if(checkList[j] == false) allTrue = false;
}
if(allTrue) return i;
}
// couldn't get to the other side of the river.
return -1;
}
}
User test case 1:
[2, [7, 6, 5, 4, 3, 2, 1]]
Analysis
expand all
Example tests
1.
0.053 s
RUNTIME ERROR,
tested program terminated unexpectedly
stderr:
Unhandled Exception: System.ArgumentOutOfRangeException: Index was out of range. Must be non-negative and less than the size of the collection. Parameter name: index at System.ThrowHelper.ThrowArgumentOutOfRangeException () [0x00000] in <filename unknown>:0 at System.Collections.Generic.List`1[System.Boolean].set_Item (Int32 index, Boolean value) [0x00000] in <filename unknown>:0 at Solution.solution (Int32 X, System.Int32[] A) [0x00000] in <filename unknown>:0 at SolutionWrapper.run (System.String input, System.String output) [0x00000] in <filename unknown>:0 at SolutionWrapper.Main (System.String[] args) [0x00000] in <filename unknown>:0 [ERROR] FATAL UNHANDLED EXCEPTION: System.ArgumentOutOfRangeException: Index was out of range. Must be non-negative and less than the size of the collection. Parameter name: index at System.ThrowHelper.ThrowArgumentOutOfRangeException () [0x00000] in <filename unknown>:0 at System.Collections.Generic.List`1[System.Boolean].set_Item (Int32 index, Boolean value) [0x00000] in <filename unknown>:0 at Solution.solution (Int32 X, System.Int32[] A) [0x00000] in <filename unknown>:0 at SolutionWrapper.run (System.String input, System.String output) [0x00000] in <filename unknown>:0 at SolutionWrapper.Main (System.String[] args) [0x00000] in <filename unknown>:0
expand all
User tests
1.
0.051 s
RUNTIME ERROR,
tested program terminated unexpectedly
stderr:
Unhandled Exception: System.ArgumentOutOfRangeException: Index was out of range. Must be non-negative and less than the size of the collection. Parameter name: index at System.ThrowHelper.ThrowArgumentOutOfRangeException () [0x00000] in <filename unknown>:0 at System.Collections.Generic.List`1[System.Boolean].set_Item (Int32 index, Boolean value) [0x00000] in <filename unknown>:0 at Solution.solution (Int32 X, System.Int32[] A) [0x00000] in <filename unknown>:0 at SolutionWrapper.run (System.String input, System.String output) [0x00000] in <filename unknown>:0 at SolutionWrapper.Main (System.String[] args) [0x00000] in <filename unknown>:0 [ERROR] FATAL UNHANDLED EXCEPTION: System.ArgumentOutOfRangeException: Index was out of range. Must be non-negative and less than the size of the collection. Parameter name: index at System.ThrowHelper.ThrowArgumentOutOfRangeException () [0x00000] in <filename unknown>:0 at System.Collections.Generic.List`1[System.Boolean].set_Item (Int32 index, Boolean value) [0x00000] in <filename unknown>:0 at Solution.solution (Int32 X, System.Int32[] A) [0x00000] in <filename unknown>:0 at SolutionWrapper.run (System.String input, System.String output) [0x00000] in <filename unknown>:0 at SolutionWrapper.Main (System.String[] args) [0x00000] in <filename unknown>:0
Code: 08:28:18 UTC,
cs,
verify,
result: Passed
using System;
using System.Collections.Generic;
class Solution {
public int solution(int X, int[] A) {
List<bool> checkList = new List<bool>();
for(int i = 0; i < X; i++)
{
checkList.Add(false);
}
for(int i = 0; i < A.Length; i++)
{
if(A[i] <= X)
{
checkList[(A[i] - 1)] = true;
}
bool allTrue = true;
for(int j = 0; j < checkList.Count; j++)
{
if(checkList[j] == false) allTrue = false;
}
if(allTrue) return i;
}
// couldn't get to the other side of the river.
return -1;
}
}
User test case 1:
[2, [7, 6, 5, 4, 3, 2, 1]]
Analysis
Code: 08:28:31 UTC,
cs,
verify,
result: Passed
using System;
using System.Collections.Generic;
class Solution {
public int solution(int X, int[] A) {
List<bool> checkList = new List<bool>();
for(int i = 0; i < X; i++)
{
checkList.Add(false);
}
for(int i = 0; i < A.Length; i++)
{
if(A[i] <= X)
{
checkList[(A[i] - 1)] = true;
}
bool allTrue = true;
for(int j = 0; j < checkList.Count; j++)
{
if(checkList[j] == false) allTrue = false;
}
if(allTrue) return i;
}
// couldn't get to the other side of the river.
return -1;
}
}
User test case 1:
[2, [7, 6, 5, 4, 3, 2, 1]]
Analysis
Code: 08:28:35 UTC,
cs,
final,
score:
63
using System;
using System.Collections.Generic;
class Solution {
public int solution(int X, int[] A) {
List<bool> checkList = new List<bool>();
for(int i = 0; i < X; i++)
{
checkList.Add(false);
}
for(int i = 0; i < A.Length; i++)
{
if(A[i] <= X)
{
checkList[(A[i] - 1)] = true;
}
bool allTrue = true;
for(int j = 0; j < checkList.Count; j++)
{
if(checkList[j] == false) allTrue = false;
}
if(allTrue) return i;
}
// couldn't get to the other side of the river.
return -1;
}
}Analysis summary
The following issues have been detected: timeout errors.
Analysis
Detected time complexity:
O(N ** 2)
expand all
Correctness tests
1.
0.057 s
OK
1.
0.057 s
OK
2.
0.057 s
OK
1.
0.056 s
OK
2.
0.056 s
OK
3.
0.057 s
OK
1.
0.055 s
OK
1.
0.057 s
OK
1.
0.056 s
OK
2.
0.056 s
OK
expand all
Performance tests
medium_random
6 and 2 random permutations, X = ~5,000
6 and 2 random permutations, X = ~5,000
✘
TIMEOUT ERROR
running time: 0.25 sec., time limit: 0.24 sec.
running time: 0.25 sec., time limit: 0.24 sec.
1.
0.251 s
TIMEOUT ERROR,
running time: 0.25 sec., time limit: 0.24 sec.
2.
0.318 s
TIMEOUT ERROR,
running time: 0.32 sec., time limit: 0.23 sec.
1.
0.176 s
OK
large_random
10 and 100 random permutation, X = ~10,000
10 and 100 random permutation, X = ~10,000
✘
TIMEOUT ERROR
running time: 2.90 sec., time limit: 0.34 sec.
running time: 2.90 sec., time limit: 0.34 sec.
1.
2.901 s
TIMEOUT ERROR,
running time: 2.90 sec., time limit: 0.34 sec.
2.
0.111 s
OK
large_permutation
permutation tests
permutation tests
✘
TIMEOUT ERROR
running time: >6.00 sec., time limit: 0.34 sec.
running time: >6.00 sec., time limit: 0.34 sec.
1.
6.000 s
TIMEOUT ERROR,
running time: >6.00 sec., time limit: 0.34 sec.
2.
6.000 s
TIMEOUT ERROR,
running time: >6.00 sec., time limit: 0.35 sec.
large_range
arithmetic sequences, X = 30,000
arithmetic sequences, X = 30,000
✘
TIMEOUT ERROR
running time: 3.84 sec., time limit: 0.27 sec.
running time: 3.84 sec., time limit: 0.27 sec.
1.
3.836 s
TIMEOUT ERROR,
running time: 3.84 sec., time limit: 0.27 sec.