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].
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int solution(int x, int[] A) {
int earliest_time = -1;
boolean found_all_leaves = false;
int[] detected_leavs = new int[x+1];
Arrays.fill(detected_leavs, 0);
int leaves_on_way = 0;
for(int i=0; i<A.length; i++) {
earliest_time++;
if(detected_leavs[A[i]] == 0 ) {
leaves_on_way++;
detected_leavs[A[i]] = 1;
}
if(leaves_on_way == x) {
found_all_leaves = true;
break;
}
} // for()
if(found_all_leaves) {
return earliest_time;
} else {
return -1;
} // if()
} // solution()
}
Solution.java:14: error: cannot find symbol Arrays.fill(detected_leavs, 0); ^ symbol: variable Arrays location: class Solution 1 error
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
import java.lang.Arrays;
class Solution {
public int solution(int x, int[] A) {
int earliest_time = -1;
boolean found_all_leaves = false;
int[] detected_leavs = new int[x+1];
Arrays.fill(detected_leavs, 0);
int leaves_on_way = 0;
for(int i=0; i<A.length; i++) {
earliest_time++;
if(detected_leavs[A[i]] == 0 ) {
leaves_on_way++;
detected_leavs[A[i]] = 1;
}
if(leaves_on_way == x) {
found_all_leaves = true;
break;
}
} // for()
if(found_all_leaves) {
return earliest_time;
} else {
return -1;
} // if()
} // solution()
}
Solution.java:7: error: cannot find symbol import java.lang.Arrays; ^ symbol: class Arrays location: package java.lang Solution.java:16: error: cannot find symbol Arrays.fill(detected_leavs, 0); ^ symbol: variable Arrays location: class Solution 2 errors
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
import java.lang.Arrays;
class Solution {
public int solution(int x, int[] A) {
int earliest_time = -1;
boolean found_all_leaves = false;
int[] detected_leavs = new int[x+1];
Arrays.fill(detected_leavs, 0);
// number of leaves that alredy lay on the way
int leaves_on_way = 0;
for(int i=0; i<A.length; i++) {
// increate the earliest time (the result value of the function)
earliest_time++;
// detection of new leaf on the way
if(detected_leavs[A[i]] == 0 ) {
leaves_on_way++;
detected_leavs[A[i]] = 1;
}
// the number of leraves on the way is equal to the position we have to reach
// so, all required leaves are on the way, break the loop, the result of
// function is the current value of the earlies_time variable
if(leaves_on_way == x) {
found_all_leaves = true;
break;
}
} // for()
/*
* return the earliest time when all leaves are on the way,
* or -1 if no there is no such a case
*/
if(found_all_leaves) {
// return the found result
return earliest_time;
} else {
// ERROR, no solution found
return -1;
} // if()
} // solution()
}
Solution.java:7: error: cannot find symbol import java.lang.Arrays; ^ symbol: class Arrays location: package java.lang Solution.java:17: error: cannot find symbol Arrays.fill(detected_leavs, 0); ^ symbol: variable Arrays location: class Solution 2 errors
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
import java.util.Arrays;
class Solution {
public int solution(int x, int[] A) {
int earliest_time = -1;
boolean found_all_leaves = false;
int[] detected_leavs = new int[x+1];
Arrays.fill(detected_leavs, 0);
// number of leaves that alredy lay on the way
int leaves_on_way = 0;
for(int i=0; i<A.length; i++) {
// increate the earliest time (the result value of the function)
earliest_time++;
// detection of new leaf on the way
if(detected_leavs[A[i]] == 0 ) {
leaves_on_way++;
detected_leavs[A[i]] = 1;
}
// the number of leraves on the way is equal to the position we have to reach
// so, all required leaves are on the way, break the loop, the result of
// function is the current value of the earlies_time variable
if(leaves_on_way == x) {
found_all_leaves = true;
break;
}
} // for()
/*
* return the earliest time when all leaves are on the way,
* or -1 if no there is no such a case
*/
if(found_all_leaves) {
// return the found result
return earliest_time;
} else {
// ERROR, no solution found
return -1;
} // if()
} // solution()
}
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
import java.util.Arrays;
class Solution {
public int solution(int x, int[] A) {
int earliest_time = -1;
boolean found_all_leaves = false;
int[] detected_leavs = new int[x+1];
Arrays.fill(detected_leavs, 0);
// number of leaves that alredy lay on the way
int leaves_on_way = 0;
for(int i=0; i<A.length; i++) {
// increate the earliest time (the result value of the function)
earliest_time++;
// detection of new leaf on the way
if(detected_leavs[A[i]] == 0 ) {
leaves_on_way++;
detected_leavs[A[i]] = 1;
}
// the number of leraves on the way is equal to the position we have to reach
// so, all required leaves are on the way, break the loop, the result of
// function is the current value of the earlies_time variable
if(leaves_on_way == x) {
found_all_leaves = true;
break;
}
} // for()
/*
* return the earliest time when all leaves are on the way,
* or -1 if no there is no such a case
*/
if(found_all_leaves) {
// return the found result
return earliest_time;
} else {
// ERROR, no solution found
return -1;
} // if()
} // solution()
}
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
import java.util.Arrays;
class Solution {
public int solution(int x, int[] A) {
int earliest_time = -1;
boolean found_all_leaves = false;
int[] detected_leavs = new int[x+1];
Arrays.fill(detected_leavs, 0);
// number of leaves that alredy lay on the way
int leaves_on_way = 0;
for(int i=0; i<A.length; i++) {
// increate the earliest time (the result value of the function)
earliest_time++;
// detection of new leaf on the way
if(detected_leavs[A[i]] == 0 ) {
leaves_on_way++;
detected_leavs[A[i]] = 1;
}
// the number of leraves on the way is equal to the position we have to reach
// so, all required leaves are on the way, break the loop, the result of
// function is the current value of the earlies_time variable
if(leaves_on_way == x) {
found_all_leaves = true;
break;
}
} // for()
/*
* return the earliest time when all leaves are on the way,
* or -1 if no there is no such a case
*/
if(found_all_leaves) {
// return the found result
return earliest_time;
} else {
// ERROR, no solution found
return -1;
} // if()
} // solution()
}
The solution obtained perfect score.