Given an array of positive integers arr[], the task is to count the minimum factor jumps required to reach the end of an array. From any particular index i, the jump can be made only for K indices where K is a factor of arr[i].
Examples:
Input: arr[] = {2, 8, 16, 55, 99, 100}
Output: 2
Explanation:
The optimal jumps are:
a) Start from 2.
b) Since factors of 2 are [1, 2]. So only 1 or 2 index jumps are available. Therefore, jump 1 index to reach 8.
c) Since factors of 8 are [1, 2, 4, 8]. So only 1, 2, 4 or 8 index jumps are available. Therefore, they jumped 4 indices to reach 100.
d) We have reached the end, so no more jumps are required.
So, 2 jumps were required.Input: arr[] = {2, 4, 6}
Output: 1
Approach: This problem can be solved using Recursion.
- Firstly, we need to precompute the factors of every number from 1 to 1000000, so that we can get different choices of jumps in O(1) time.
- Then, recursively calculate the minimum jumps required to reach the end of the array and print it.
C++
// C++ code to count minimum factor jumps// to reach the end of array#include <bits/stdc++.h>using namespace std;// vector to store factors of each integervector<int> factors[100005];// Precomputing all factors of integers// from 1 to 100000void precompute(){ for (int i = 1; i <= 100000; i++) { for (int j = i; j <= 100000; j += i) { factors[j].push_back(i); } }}// Recursive function to count the minimum jumpsint solve(int arr[], int k, int n){ // If we reach the end of array, // no more jumps are required if (k == n - 1) { return 0; } // If the jump results in out of index, // return INT_MAX if (k >= n) { return INT_MAX; } // Else compute the answer // using the recurrence relation int ans = INT_MAX; // Iterating over all choices of jumps for (auto j : factors[arr[k]]) { // Considering current factor as a jump int res = solve(arr, k + j, n); // Jump leads to the destination if (res != INT_MAX) { ans = min(ans, res + 1); } } // Return ans return ans;}// Driver codeint main(){ // pre-calculating the factors precompute(); int arr[] = { 2, 8, 16, 55, 99, 100 }; int n = sizeof(arr) / sizeof(arr[0]); cout << solve(arr, 0, n);} |
Java
// Java code to count minimum // factor jumps to reach the // end of arrayimport java.util.*;public class GFG{// vector to store factors // of each integerstatic Vector<Integer> []factors = new Vector[100005];// Precomputing all factors // of integers from 1 to 100000static void precompute(){ for (int i = 0; i < factors.length; i++) factors[i] = new Vector<Integer>(); for (int i = 1; i <= 100000; i++) { for (int j = i; j <= 100000; j += i) { factors[j].add(i); } }}// Function to count the // minimum jumpsstatic int solve(int arr[], int k, int n){ // If we reach the end of // array, no more jumps // are required if (k == n - 1) { return 0; } // If the jump results in // out of index, return // Integer.MAX_VALUE if (k >= n) { return Integer.MAX_VALUE; } // Else compute the answer // using the recurrence relation int ans = Integer.MAX_VALUE; // Iterating over all choices // of jumps for (int j : factors[arr[k]]) { // Considering current factor // as a jump int res = solve(arr, k + j, n); // Jump leads to the destination if (res != Integer.MAX_VALUE) { ans = Math.min(ans, res + 1); } } // Return ans return ans;}// Driver codepublic static void main(String[] args){ // pre-calculating // the factors precompute(); int arr[] = {2, 8, 16, 55, 99, 100}; int n = arr.length; System.out.print(solve(arr, 0, n));}}// This code is contributed by Samim Hossain Mondal. |
C#
// C# code to count minimum // factor jumps to reach the // end of arrayusing System;using System.Collections.Generic;class GFG{// vector to store factors // of each integerstatic List<int> []factors = new List<int>[100005];// Precomputing all factors // of integers from 1 to 100000static void precompute(){ for (int i = 0; i < factors.Length; i++) factors[i] = new List<int>(); for (int i = 1; i <= 100000; i++) { for (int j = i; j <= 100000; j += i) { factors[j].Add(i); } }}// Function to count the // minimum jumpsstatic int solve(int []arr, int k, int n){ // If we reach the end of // array, no more jumps // are required if (k == n - 1) { return 0; } // If the jump results in // out of index, return // int.MaxValue if (k >= n) { return int.MaxValue; } // Else compute the answer // using the recurrence relation int ans = int.MaxValue; // Iterating over all choices // of jumps foreach (int j in factors[arr[k]]) { // Considering current // factor as a jump int res = solve(arr, k + j, n); // Jump leads to the // destination if (res != int.MaxValue) { ans = Math.Min(ans, res + 1); } } // Return ans return ans;}// Driver codepublic static void Main(String[] args){ // pre-calculating // the factors precompute(); int []arr = {2, 8, 16, 55, 99, 100}; int n = arr.Length; Console.Write(solve(arr, 0, n));}}// This code is contributed by Samim Hossain Mondal. |
Python
# Python3 code to count minimum factor jumps# to reach the end of array# vector to store factors of each integerfactors = [[] for i in range(100005)]# Precomputing all factors of integers# from 1 to 100000def precompute(): for i in range(1, 100001): for j in range(i, 100001, i): factors[j].append(i)# Function to count the minimum jumpsdef solve(arr, k, n): # If we reach the end of array, # no more jumps are required if (k == n - 1): return 0 # If the jump results in out of index, # return INT_MAX if (k >= n): return 1000000000 # Else compute the answer # using the recurrence relation ans = 1000000000 # Iterating over all choices of jumps for j in factors[arr[k]]: # Considering current factor as a jump res = solve(arr, k + j, n) # Jump leads to the destination if (res != 1000000000): ans = min(ans, res + 1) # Return ans return ans# Driver codeif __name__ == '__main__': # pre-calculating the factors precompute() arr = [2, 8, 16, 55, 99, 100] n = len(arr) print(solve(arr, 0, n))# This code is contributed by Samim Hossain Mondal. |
Javascript
<script>// Javascript code to count minimum factor jumps// to reach the end of array// vector to store factors of each integerlet factors = new Array();for (let i = 0; i < 100005; i++) { factors.push(new Array());}// Precomputing all factors of integers// from 1 to 100000function precompute() { for (let i = 1; i <= 100000; i++) { for (let j = i; j <= 100000; j += i) { factors[j].push(i); } }}// Function to count the minimum jumpsfunction solve(arr, k, n) { // If we reach the end of array, // no more jumps are required if (k == n - 1) { return 0; } // If the jump results in out of index, // return INT_MAX if (k >= n) { return Number.MAX_SAFE_INTEGER; } // Else compute the answer // using the recurrence relation let ans = Number.MAX_SAFE_INTEGER; // Iterating over all choices of jumps for (let j of factors[arr[k]]) { // Considering current factor as a jump let res = solve(arr, k + j, n); // Jump leads to the destination if (res != Number.MAX_SAFE_INTEGER) { ans = Math.min(ans, res + 1); } } // Return ans return ans;}// Driver code// pre-calculating the factorsprecompute();let arr = [2, 8, 16, 55, 99, 100];let n = arr.length;document.write(solve(arr, 0, n));// This code is contributed by Samim Hossain Mondal.</script> |
Output
2
Time Complexity: O(100005*2N)
Auxiliary Space: O(100005)
Another Approach: Dynamic Programming using Memoization.
- Firstly, we need to precompute the factors of every number from 1 to 1000000, so that we can get different choices of jumps in O(1) time.
- Then, let dp[i] be the minimum jump required to reach i, we need to find dp[n-1].
- So, the recurrence relation becomes:
where j is one of the factors of arr[i] & solve() is the recursive function
![dp[i] = min(dp[i], 1 + solve(i+j))](https://geeksforgeeks.org/wp-content/uploads/2023/11/dominic_rubhabha_quicklatex.com-194368907ec895986c58c129a7b4f30c_l3.png "Rendered by QuickLaTeX.com")
- Find the minimum jumps using this recurrence relation and print it.
Below is the recursive implementation of the above approach:
C++
// C++ code to count minimum factor jumps// to reach the end of array#include <bits/stdc++.h>using namespace std;// vector to store factors of each integervector<int> factors[100005];// dp arrayint dp[100005];// Precomputing all factors of integers// from 1 to 100000void precompute(){ for (int i = 1; i <= 100000; i++) { for (int j = i; j <= 100000; j += i) { factors[j].push_back(i); } }}// Function to count the minimum jumpsint solve(int arr[], int k, int n){ // If we reach the end of array, // no more jumps are required if (k == n - 1) { return 0; } // If the jump results in out of index, // return INT_MAX if (k >= n) { return INT_MAX; } // If the answer has been already computed, // return it directly if (dp[k]) { return dp[k]; } // Else compute the answer // using the recurrence relation int ans = INT_MAX; // Iterating over all choices of jumps for (auto j : factors[arr[k]]) { // Considering current factor as a jump int res = solve(arr, k + j, n); // Jump leads to the destination if (res != INT_MAX) { ans = min(ans, res + 1); } } // Return ans and memorize it return dp[k] = ans;}// Driver codeint main(){ // pre-calculating the factors precompute(); int arr[] = { 2, 8, 16, 55, 99, 100 }; int n = sizeof(arr) / sizeof(arr[0]); cout << solve(arr, 0, n);} |
Java
// Java code to count minimum // factor jumps to reach the // end of arrayimport java.util.*;class GFG{// vector to store factors // of each integerstatic Vector<Integer> []factors = new Vector[100005];// dp arraystatic int []dp = new int[100005];// Precomputing all factors // of integers from 1 to 100000static void precompute(){ for (int i = 0; i < factors.length; i++) factors[i] = new Vector<Integer>(); for (int i = 1; i <= 100000; i++) { for (int j = i; j <= 100000; j += i) { factors[j].add(i); } }}// Function to count the // minimum jumpsstatic int solve(int arr[], int k, int n){ // If we reach the end of // array, no more jumps // are required if (k == n - 1) { return 0; } // If the jump results in // out of index, return // Integer.MAX_VALUE if (k >= n) { return Integer.MAX_VALUE; } // If the answer has been // already computed, return // it directly if (dp[k] != 0) { return dp[k]; } // Else compute the answer // using the recurrence relation int ans = Integer.MAX_VALUE; // Iterating over all choices // of jumps for (int j : factors[arr[k]]) { // Considering current factor // as a jump int res = solve(arr, k + j, n); // Jump leads to the destination if (res != Integer.MAX_VALUE) { ans = Math.min(ans, res + 1); } } // Return ans and memorize it return dp[k] = ans;}// Driver codepublic static void main(String[] args){ // pre-calculating // the factors precompute(); int arr[] = {2, 8, 16, 55, 99, 100}; int n = arr.length; System.out.print(solve(arr, 0, n));}}// This code is contributed by Rajput-Ji |
Python3
# Python3 code to count minimum factor jumps# to reach the end of array # vector to store factors of each integerfactors= [[] for i in range(100005)]; # dp arraydp = [0 for i in range(100005)]; # Precomputing all factors of integers# from 1 to 100000def precompute(): for i in range(1, 100001): for j in range(i, 100001, i): factors[j].append(i); # Function to count the minimum jumpsdef solve(arr, k, n): # If we reach the end of array, # no more jumps are required if (k == n - 1): return 0; # If the jump results in out of index, # return INT_MAX if (k >= n): return 1000000000 # If the answer has been already computed, # return it directly if (dp[k]): return dp[k]; # Else compute the answer # using the recurrence relation ans = 1000000000 # Iterating over all choices of jumps for j in factors[arr[k]]: # Considering current factor as a jump res = solve(arr, k + j, n); # Jump leads to the destination if (res != 1000000000): ans = min(ans, res + 1); # Return ans and memorize it dp[k] = ans; return ans# Driver codeif __name__=='__main__': # pre-calculating the factors precompute() arr = [ 2, 8, 16, 55, 99, 100 ] n = len(arr) print(solve(arr, 0, n)) # This code is contributed by rutvik_56 |
C#
// C# code to count minimum // factor jumps to reach the // end of arrayusing System;using System.Collections.Generic;class GFG{// vector to store factors // of each integerstatic List<int> []factors = new List<int>[100005];// dp arraystatic int []dp = new int[100005];// Precomputing all factors // of integers from 1 to 100000static void precompute(){ for (int i = 0; i < factors.Length; i++) factors[i] = new List<int>(); for (int i = 1; i <= 100000; i++) { for (int j = i; j <= 100000; j += i) { factors[j].Add(i); } }}// Function to count the // minimum jumpsstatic int solve(int []arr, int k, int n){ // If we reach the end of // array, no more jumps // are required if (k == n - 1) { return 0; } // If the jump results in // out of index, return // int.MaxValue if (k >= n) { return int.MaxValue; } // If the answer has been // already computed, return // it directly if (dp[k] != 0) { return dp[k]; } // Else compute the answer // using the recurrence relation int ans = int.MaxValue; // Iterating over all choices // of jumps foreach (int j in factors[arr[k]]) { // Considering current // factor as a jump int res = solve(arr, k + j, n); // Jump leads to the // destination if (res != int.MaxValue) { ans = Math.Min(ans, res + 1); } } // Return ans and // memorize it return dp[k] = ans;}// Driver codepublic static void Main(String[] args){ // pre-calculating // the factors precompute(); int []arr = {2, 8, 16, 55, 99, 100}; int n = arr.Length; Console.Write(solve(arr, 0, n));}}// This code is contributed by shikhasingrajput |
Javascript
<script>// Javascript code to count minimum factor jumps// to reach the end of array// vector to store factors of each integerlet factors = new Array();// dp arraylet dp = new Array(100005);for (let i = 0; i < 100005; i++) { factors.push(new Array());}// Precomputing all factors of integers// from 1 to 100000function precompute() { for (let i = 1; i <= 100000; i++) { for (let j = i; j <= 100000; j += i) { factors[j].push(i); } }}// Function to count the minimum jumpsfunction solve(arr, k, n) { // If we reach the end of array, // no more jumps are required if (k == n - 1) { return 0; } // If the jump results in out of index, // return INT_MAX if (k >= n) { return Number.MAX_SAFE_INTEGER; } // If the answer has been already computed, // return it directly if (dp[k]) { return dp[k]; } // Else compute the answer // using the recurrence relation let ans = Number.MAX_SAFE_INTEGER; // Iterating over all choices of jumps for (let j of factors[arr[k]]) { // Considering current factor as a jump let res = solve(arr, k + j, n); // Jump leads to the destination if (res != Number.MAX_SAFE_INTEGER) { ans = Math.min(ans, res + 1); } } // Return ans and memorize it return dp[k] = ans;}// Driver code// pre-calculating the factorsprecompute();let arr = [2, 8, 16, 55, 99, 100];let n = arr.length;document.write(solve(arr, 0, n));// This code is contributed by _saurabh_jaiswal</script> |
Output
2
Time Complexity: O(100000*N)
Auxiliary Space: O(100005)
Given below is the Iterative Bottom-Up Approach:
C++
// C++ program for bottom up approach#include <bits/stdc++.h>using namespace std;// Vector to store factors of each integervector<int> factors[100005];// Initialize the dp arrayint dp[100005];// Precompute all the// factors of every integervoid precompute(){ for (int i = 1; i <= 100000; i++) { for (int j = i; j <= 100000; j += i) factors[j].push_back(i); }}// Function to count the// minimum factor jumpint solve(int arr[], int n){ // Initialise minimum jumps to // reach each cell as INT_MAX for (int i = 0; i <= 100005; i++) { dp[i] = INT_MAX; } // 0 jumps required to // reach the first cell dp[0] = 0; // Iterate over all cells for (int i = 0; i < n; i++) { // calculating for each jump for (auto j : factors[arr[i]]) { // If a cell is in bound if (i + j < n) dp[i + j] = min(dp[i + j], 1 + dp[i]); } } // Return minimum jumps // to reach last cell return dp[n - 1];}// Driver codeint main(){ // Pre-calculating the factors precompute(); int arr[] = { 2, 8, 16, 55, 99, 100 }; int n = sizeof(arr) / sizeof(arr[0]); // Function call cout << solve(arr, n);} |
Java
// Java program for bottom up approachimport java.util.*;class GFG{// Vector to store factors of each integer@SuppressWarnings("unchecked")static Vector<Integer> []factors = new Vector[100005];// Initialize the dp arraystatic int []dp = new int[100005];// Precompute all the// factors of every integerstatic void precompute(){ for(int i = 1; i <= 100000; i++) { for(int j = i; j <= 100000; j += i) factors[j].add(i); }}// Function to count the// minimum factor jumpstatic int solve(int arr[], int n){ // Initialise minimum jumps to // reach each cell as Integer.MAX_VALUE for(int i = 0; i < 100005; i++) { dp[i] = Integer.MAX_VALUE; } // 0 jumps required to // reach the first cell dp[0] = 0; // Iterate over all cells for(int i = 0; i < n; i++) { // Calculating for each jump for(int j : factors[arr[i]]) { // If a cell is in bound if (i + j < n) dp[i + j] = Math.min(dp[i + j], 1 + dp[i]); } } // Return minimum jumps // to reach last cell return dp[n - 1];}// Driver codepublic static void main(String[] args){ for(int i = 0; i < factors.length; i++) factors[i] = new Vector<Integer>(); // Pre-calculating the factors precompute(); int arr[] = { 2, 8, 16, 55, 99, 100 }; int n = arr.length; // Function call System.out.print(solve(arr, n));}}// This code is contributed by Princi Singh |
Python3
# Python3 program for bottom up approach # Vector to store factors of each integerfactors=[[] for i in range(100005)]; # Initialize the dp arraydp=[1000000000 for i in range(100005)]; # Precompute all the# factors of every integerdef precompute(): for i in range(1, 100001): for j in range(i, 100001, i): factors[j].append(i); # Function to count the# minimum factor jumpdef solve(arr, n): # 0 jumps required to # reach the first cell dp[0] = 0; # Iterate over all cells for i in range(n): # calculating for each jump for j in factors[arr[i]]: # If a cell is in bound if (i + j < n): dp[i + j] = min(dp[i + j], 1 + dp[i]); # Return minimum jumps # to reach last cell return dp[n - 1]; # Driver codeif __name__=='__main__': # Pre-calculating the factors precompute(); arr = [ 2, 8, 16, 55, 99, 100 ] n=len(arr) # Function call print(solve(arr,n)) # This code is contributed by pratham76 |
C#
// C# program for bottom up approachusing System;using System.Collections.Generic;class GFG{ // Vector to store factors of each integerstatic List<List<int>> factors = new List<List<int>>();// Initialize the dp arraystatic int[] dp;// Precompute all the// factors of every integerstatic void precompute(){ for(int i = 1; i <= 100000; i++) { for(int j = i; j <= 100000; j += i) factors[j].Add(i); }}// Function to count the// minimum factor jumpstatic int solve(int[] arr, int n){ // Initialise minimum jumps to // reach each cell as Integer.MAX_VALUE for(int i = 0; i < 100005; i++) { dp[i] = int.MaxValue; } // 0 jumps required to // reach the first cell dp[0] = 0; // Iterate over all cells for(int i = 0; i < n; i++) { // Calculating for each jump foreach(int j in factors[arr[i]]) { // If a cell is in bound if (i + j < n) dp[i + j] = Math.Min(dp[i + j], 1 + dp[i]); } } // Return minimum jumps // to reach last cell return dp[n - 1];}// Driver codestatic public void Main (){ for(int i = 0; i < 100005; i++) factors.Add(new List<int>()); dp = new int[100005]; // Pre-calculating the factors precompute(); int[] arr = { 2, 8, 16, 55, 99, 100 }; int n = arr.Length; // Function call Console.Write(solve(arr, n));}}// This code is contributed by offbeat |
Javascript
<script>// Javascript program for bottom up approach// Vector to store factors of each integervar factors = Array.from(Array(100005), ()=>Array());// Initialize the dp arrayvar dp = Array(100005);// Precompute all the// factors of every integerfunction precompute(){ for (var i = 1; i <= 100000; i++) { for (var j = i; j <= 100000; j += i) factors[j].push(i); }}// Function to count the// minimum factor jumpfunction solve(arr, n){ // Initialise minimum jumps to // reach each cell as INT_MAX for (var i = 0; i <= 100005; i++) { dp[i] = 1000000000; } // 0 jumps required to // reach the first cell dp[0] = 0; // Iterate over all cells for (var i = 0; i < n; i++) { // calculating for each jump for (var j of factors[arr[i]]) { // If a cell is in bound if (i + j < n) dp[i + j] = Math.min(dp[i + j], 1 + dp[i]); } } // Return minimum jumps // to reach last cell return dp[n - 1];} // Driver code // Pre-calculating the factors precompute(); var arr = [2, 8, 16, 55, 99, 100]; var n = arr.length // Function call document.write( solve(arr, n));</script> |
Output
2
Time Complexity: O(N2)
Auxiliary Space: O(100005)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
