{"id":"64410c7f-59ca-4405-9cdf-b3dae46f876a","name":"Frog Jump","description":"1. You are given an array of positive integers in ascending order, which represents the position of stones in the river.\r\n2. A frog is trying to cross a river. It can jump on a stone, but it must not jump into the water.\r\n3. You have to find if the frog can cross the river by landing on the last stone.\r\n4. The frog is on the first stone initially, and from first stone it can jump 1 unit only.\r\n5. The frog can only jump k-1, k, or k+1 units in the forward direction, where k is the frog's last jump.","inputFormat":"A number N \r\na1\r\na2.. N numbers","outputFormat":"true/false","constraints":"2 &lt;= n &lt;= 2000\r\n0 &lt;= a[i] &lt; 2^31\r\na[0] = 0","sampleCode":{"cpp":{"code":""},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n\r\n public static boolean solution(int[] stones) {\r\n // write your code here\r\n\r\n }\r\n\r\n public static void main(String[] args) {\r\n Scanner scn = new Scanner(System.in);\r\n int n = scn.nextInt();\r\n int[] arr = new int[n];\r\n for (int i = 0 ; i < n; i++) {\r\n arr[i] = scn.nextInt();\r\n }\r\n\r\n System.out.println(solution(arr));\r\n }\r\n\r\n}"},"ruby":{"code":""},"python":{"code":""},"javascript":{"code":""}},"points":10,"difficulty":"hard","sampleInput":"8\r\n0 1 3 5 6 8 12 17","sampleOutput":"true\r\n","questionVideo":"","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"5539a6e8-c8bf-4f04-805c-e43e9d20e72a","name":"Dynamic Programming For Intermediate","slug":"dynamic-programming-for-intermediate-408","type":0},{"id":"0565ef75-6d57-441e-979e-94ffeff63c46","name":"Frog Jump","slug":"frog-jump","type":1}],"next":{"id":"45f5107e-dc61-4d72-8d1f-77252cce8180","name":"Interleaving Of Two Strings","type":1,"slug":"interleaving-of-two-strings"},"prev":{"id":"351ded63-248f-4ca0-b6bd-1ef265a86635","name":"Find Water In Glass","type":1,"slug":"find-water-in-glass"}}}

Frog Jump

1. You are given an array of positive integers in ascending order, which represents the position of stones in the river. 2. A frog is trying to cross a river. It can jump on a stone, but it must not jump into the water. 3. You have to find if the frog can cross the river by landing on the last stone. 4. The frog is on the first stone initially, and from first stone it can jump 1 unit only. 5. The frog can only jump k-1, k, or k+1 units in the forward direction, where k is the frog's last jump.

{"id":"64410c7f-59ca-4405-9cdf-b3dae46f876a","name":"Frog Jump","description":"1. You are given an array of positive integers in ascending order, which represents the position of stones in the river.\r\n2. A frog is trying to cross a river. It can jump on a stone, but it must not jump into the water.\r\n3. You have to find if the frog can cross the river by landing on the last stone.\r\n4. The frog is on the first stone initially, and from first stone it can jump 1 unit only.\r\n5. The frog can only jump k-1, k, or k+1 units in the forward direction, where k is the frog's last jump.","inputFormat":"A number N \r\na1\r\na2.. N numbers","outputFormat":"true/false","constraints":"2 &lt;= n &lt;= 2000\r\n0 &lt;= a[i] &lt; 2^31\r\na[0] = 0","sampleCode":{"cpp":{"code":""},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n\r\n public static boolean solution(int[] stones) {\r\n // write your code here\r\n\r\n }\r\n\r\n public static void main(String[] args) {\r\n Scanner scn = new Scanner(System.in);\r\n int n = scn.nextInt();\r\n int[] arr = new int[n];\r\n for (int i = 0 ; i < n; i++) {\r\n arr[i] = scn.nextInt();\r\n }\r\n\r\n System.out.println(solution(arr));\r\n }\r\n\r\n}"},"ruby":{"code":""},"python":{"code":""},"javascript":{"code":""}},"points":10,"difficulty":"hard","sampleInput":"8\r\n0 1 3 5 6 8 12 17","sampleOutput":"true\r\n","questionVideo":"","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"5539a6e8-c8bf-4f04-805c-e43e9d20e72a","name":"Dynamic Programming For Intermediate","slug":"dynamic-programming-for-intermediate-408","type":0},{"id":"0565ef75-6d57-441e-979e-94ffeff63c46","name":"Frog Jump","slug":"frog-jump","type":1}],"next":{"id":"45f5107e-dc61-4d72-8d1f-77252cce8180","name":"Interleaving Of Two Strings","type":1,"slug":"interleaving-of-two-strings"},"prev":{"id":"351ded63-248f-4ca0-b6bd-1ef265a86635","name":"Find Water In Glass","type":1,"slug":"find-water-in-glass"}}}
plane

Editor


Loading...

Frog Jump

hard

1. You are given an array of positive integers in ascending order, which represents the position of stones in the river. 2. A frog is trying to cross a river. It can jump on a stone, but it must not jump into the water. 3. You have to find if the frog can cross the river by landing on the last stone. 4. The frog is on the first stone initially, and from first stone it can jump 1 unit only. 5. The frog can only jump k-1, k, or k+1 units in the forward direction, where k is the frog's last jump.

Constraints

2 <= n <= 2000 0 <= a[i] < 2^31 a[0] = 0

Format

Input

A number N a1 a2.. N numbers

Output

true/false

Example

Sample Input

8 0 1 3 5 6 8 12 17

Sample Output

true

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode