Minimise jumps to reach end of Array by jumping in range [x, x+k]
Given an array arr[] of size N and an integer k. Return True, otherwise False, if there’s any way to reach the last element of arr[] by satisfying the following conditions:
- Only move in the forward direction.
- Initially, we can increase only by 1 from the first element.
- We are allowed to increment by x + 1, x + 2, x + 3….., x+ k, where x is the last increment.
Examples:
Input: N = 8, arr[] = {0, 1, 3, 5, 6, 8, 12, 17}, k = 3
Output: False
Explanation: Can reach the 12th position but can not reach the 17th position. Since it cannot land at the last wood so, we will return false.Input: N = 8, arr[] = {0, 1, 2, 3, 4, 11, 13, 15}, k = 3
Output: False
Explanation: We can not reach from the 4th position to the wood at the 11th position in any way by following the constraints. So, we will return false.
Approach: The above problem can be solved with the below idea:
We will take a map that consists of an integer as key ( which are the positions of the arr[]) and a set as value ( which denotes the possible increments from that position). For each position of the arr[] we will keep a track of possible increments from that position and by doing this if we reach the last element we will return True else, we will return False.
Steps involved in the implementation of the approach:
- Add elements of arr[] along with their respective sets in map mp.
- Sets will store increments possible from that particular element.
- For each element, iterate over the set and increment by k for each possible increment.
- If any increment reaches the last element, Return True, Otherwise False.
Below is the implementation of the above approach:
C++
// C++ Implementation of the above approach #include <bits/stdc++.h> using namespace std; // Function to calculate if its possible // to reach last element string solve(vector< int >& v, int n, int k) { map< int , set< int > > mp; // Adding all elements to map for ( int i = 0; i < n; i++) { set< int > s; mp[v[i]] = s; } // From first element only // we can increment 1 mp[v[0]].insert(1); // To check all possible ways for ( int i = 0; i < n; i++) { int curr_stone = v[i]; set< int > jumps = mp[curr_stone]; for ( auto jump : jumps) { int idx = curr_stone + jump; // If last element is reached if (idx == v[n - 1]) { return "True" ; } if (mp.find(idx) != mp.end()) { // Upto k jumps possible from // last increment for ( int i = 1; i <= k; i++) { mp[idx].insert(jump + i); } } } } // Not possible return "False" ; } // Driver Code int main() { // Input int n = 5; vector< int > v = { 0, 1, 2, 3, 4 }; int k = 2; // Function call cout << solve(v, n, k) << endl; return 0; } |
Java
import java.util.*; class Main { // Function to calculate if its possible // to reach last element public static String solve(List<Integer> v, int n, int k) { Map<Integer, Set<Integer>> mp = new HashMap<>(); // Adding all elements to map for ( int i = 0 ; i < n; i++) { Set<Integer> s = new HashSet<>(); mp.put(v.get(i), s); } // From first element only // we can increment 1 mp.get(v.get( 0 )).add( 1 ); // To check all possible ways for ( int i = 0 ; i < n; i++) { int curr_stone = v.get(i); Set<Integer> jumps = mp.get(curr_stone); for (Integer jump : jumps) { int idx = curr_stone + jump; // If last element is reached if (idx == v.get(n - 1 )) { return "True" ; } if (mp.containsKey(idx)) { // Upto k jumps possible from // last increment for ( int j = 1 ; j <= k; j++) { mp.get(idx).add(jump + j); } } } } // Not possible return "False" ; } public static void main(String[] args) { // Input int n = 5 ; List<Integer> v = Arrays.asList( 0 , 1 , 2 , 3 , 4 ); int k = 2 ; // Function call System.out.println(solve(v, n, k)); } } // This code is contributed by adityamaharshi21. |
Python3
from collections import defaultdict from typing import List def solve(v: List [ int ], n: int , k: int ) - > str : # use defaultdict to create a map where each key will have a set as its value mp = defaultdict( set ) # Adding all elements to map for i in range (n): mp[v[i]] # From first element only # we can increment 1 mp[v[ 0 ]].add( 1 ) # To check all possible ways for i in range (n): curr_stone = v[i] jumps = mp[curr_stone] for jump in jumps: idx = curr_stone + jump # If last element is reached if idx = = v[n - 1 ]: return "True" if idx in mp: # Upto k jumps possible from last increment for i in range ( 1 , k + 1 ): mp[idx].add(jump + i) # Not possible return "False" # Test v = [ 0 , 1 , 2 , 3 , 4 ] n = len (v) k = 2 print (solve(v, n, k)) # This code is contributed by lokeshpotta20. |
C#
// C# code to implement the approach using System; using System.Collections.Generic; class GFG { // Function to calculate if its possible // to reach last element static string solve(List< int > v, int n, int k) { Dictionary< int , SortedSet< int > > mp= new Dictionary< int , SortedSet< int > >(); // Adding all elements to map for ( int i = 0; i < n; i++) { SortedSet< int > s= new SortedSet< int >(); mp.Add(v[i], s); } // From first element only // we can increment 1 mp[v[0]].Add(1); // To check all possible ways for ( int i = 0; i < n; i++) { int curr_stone = v[i]; SortedSet< int > jumps = mp[curr_stone]; foreach ( var jump in jumps){ int idx = curr_stone + jump; // If last element is reached if (idx == v[n - 1]) { return "True" ; } if (mp.ContainsKey(idx)) { // Upto k jumps possible from // last increment for ( int j = 1; j <= k; j++) { mp[idx].Add(jump + j); } } } } // Not possible return "False" ; } // Driver Code public static void Main() { // Input int n = 5; List< int > v = new List< int >{ 0, 1, 2, 3, 4 }; int k = 2; // Function call Console.Write(solve(v, n, k)); } } // This code is contributed by poojaagrawal2. |
Javascript
// JavaScript Implementation of the above approach // Function to calculate if its possible // to reach last element function solve(v, n, k) { let mp = new Map(); // Adding all elements to map for (let i = 0; i < n; i++) { let s = new Set(); mp.set(v[i], s); } // From first element only // we can increment 1 mp.get(v[0]).add(1); // To check all possible ways for (let i = 0; i < n; i++) { let curr_stone = v[i]; let jumps = Array.from(mp.get(curr_stone)); for (let jump of jumps) { let idx = curr_stone + jump; // If last element is reached if (idx === v[n - 1]) { return "True" ; } if (mp.has(idx)) { // Upto k jumps possible from // last increment for (let i = 1; i <= k; i++) { mp.get(idx).add(jump + i); } } } } // Not possible return "False" ; } // Driver Code let n = 5; let v = [0, 1, 2, 3, 4]; let k = 2; // Function call console.log(solve(v, n, k)); // This code is contributed by rutikbhosale. |
True
Time Complexity: O(N^2)
Auxiliary Space: O(N* K)
Related Articles:
Contact Us