Given an integer N, the task is to find the minimum number of operations needed to obtain the number N starting from 1. Below are the operations:
- Add 1 to the current number.
- Multiply the current number by 2.
- Multiply the current number by 3.
Print the minimum number of operations required and the corresponding sequence to obtain N.
Examples:
Input: N = 3
Output:
1
1 3
Explanation:
Operation 1: Multiply 1 * 3 = 3.
Hence, only 1 operation is required.Input: N = 5
Output:
3
1 2 4 5
Explanation:
The minimum required operations are as follows:
1 * 2 -> 2
2 * 2 -> 4
4 + 1 -> 5
Recursive Approach: Recursively generate every possible combination to reduce N to 1 and calculate the number of operations required. Finally, after exhausting all possible combinations, print the sequence that required the minimum number of operations.
Below is the implementation of the above approach:
C++
// C++ program to implement // the above approach #include <bits/stdc++.h> using namespace std; vector<int> find_sequence(int n) { // Base Case if (n == 1) return {1, -1}; // Recursive Call for n-1 auto arr = find_sequence(n - 1); vector<int> ans = {arr[0] + 1, n - 1}; // Check if n is divisible by 2 if (n % 2 == 0) { vector<int> div_by_2 = find_sequence(n / 2); if (div_by_2[0] < ans[0]) ans = {div_by_2[0] + 1, n / 2}; } // Check if n is divisible by 3 if (n % 3 == 0) { vector<int> div_by_3 = find_sequence(n / 3); if (div_by_3[0] < ans[0]) vector<int> ans = {div_by_3[0] + 1, n / 3}; } // Returns a tuple (a, b), where // a: Minimum steps to obtain x from 1 // b: Previous number return ans; } // Function that find the optimal // solution vector<int> find_solution(int n) { auto a = find_sequence(n); // Print the length cout << a[0] << endl; vector<int> sequence; sequence.push_back(n); //Exit condition for loop = -1 //when n has reached 1 while (a[1] != -1) { sequence.push_back(a[1]); auto arr = find_sequence(a[1]); a[1] = arr[1]; } // Return the sequence // in reverse order reverse(sequence.begin(), sequence.end()); return sequence; } // Driver Code int main() { // Given N int n = 5; // Function call auto i = find_solution(n); for(int j : i) cout << j << " "; } // This code is contributed by mohit kumar 29 |
Java
// Java program to implement // the above approach import java.util.*; import java.util.Collections; import java.util.Vector; //Vector<Integer> v = new Vector<Integer>(n); class GFG{ static Vector<Integer> find_sequence(int n) { Vector<Integer> temp = new Vector<Integer>(); temp.add(1); temp.add(-1); // Base Case if (n == 1) return temp; // Recursive Call for n-1 Vector<Integer> arr = find_sequence(n - 1); Vector<Integer> ans = new Vector<Integer>(n); ans.add(arr.get(0) + 1); ans.add(n - 1); // Check if n is divisible by 2 if (n % 2 == 0) { Vector<Integer> div_by_2 = find_sequence(n / 2); if (div_by_2.get(0) < ans.get(0)) { ans.clear(); ans.add(div_by_2.get(0) + 1); ans.add(n / 2); } } // Check if n is divisible by 3 if (n % 3 == 0) { Vector<Integer> div_by_3 = find_sequence(n / 3); if (div_by_3.get(0) < ans.get(0)) { ans.clear(); ans.add(div_by_3.get(0) + 1); ans.add(n / 3); } } // Returns a tuple (a, b), where // a: Minimum steps to obtain x from 1 // b: Previous number return ans; } // Function that find the optimal // solution static Vector<Integer> find_solution(int n) { Vector<Integer> a = find_sequence(n); // Print the length System.out.println(a.get(0)); Vector<Integer> sequence = new Vector<Integer>(); sequence.add(n); // Exit condition for loop = -1 // when n has reached 1 while (a.get(1) != -1) { sequence.add(a.get(1)); Vector<Integer> arr = find_sequence(a.get(1)); a.set(1, arr.get(1)); } // Return the sequence // in reverse order Collections.reverse(sequence); return sequence; } // Driver Code public static void main(String args[]) { // Given N int n = 5; // Function call Vector<Integer> res = find_solution(n); for(int i = 0; i < res.size(); i++) { System.out.print(res.get(i) + " "); } } } // This code is contributed by Surendra_Gangwar |
Python3
# Python3 program to implement # the above approach def find_sequence(n): # Base Case if n == 1: return 1, -1 # Recursive Call for n-1 ans = (find_sequence(n - 1)[0] + 1, n - 1) # Check if n is divisible by 2 if n % 2 == 0: div_by_2 = find_sequence(n // 2) if div_by_2[0] < ans[0]: ans = (div_by_2[0] + 1, n // 2) # Check if n is divisible by 3 if n % 3 == 0: div_by_3 = find_sequence(n // 3) if div_by_3[0] < ans[0]: ans = (div_by_3[0] + 1, n // 3) # Returns a tuple (a, b), where # a: Minimum steps to obtain x from 1 # b: Previous number return ans # Function that find the optimal # solution def find_solution(n): a, b = find_sequence(n) # Print the length print(a) sequence = [] sequence.append(n) # Exit condition for loop = -1 # when n has reached 1 while b != -1: sequence.append(b) _, b = find_sequence(b) # Return the sequence # in reverse order return sequence[::-1] # Driver Code # Given N n = 5 # Function Call print(*find_solution(n)) |
C#
// C# program to implement // the above approach using System; using System.Collections.Generic; class GFG{ static List<int> find_sequence(int n) { List<int> temp = new List<int>(); temp.Add(1); temp.Add(-1); // Base Case if (n == 1) return temp; // Recursive Call for n-1 List<int> arr = find_sequence(n - 1); List<int> ans = new List<int>(n); ans.Add(arr[0] + 1); ans.Add(n - 1); // Check if n is divisible by 2 if (n % 2 == 0) { List<int> div_by_2 = find_sequence(n / 2); if (div_by_2[0] < ans[0]) { ans.Clear(); ans.Add(div_by_2[0] + 1); ans.Add(n / 2); } } // Check if n is divisible // by 3 if (n % 3 == 0) { List<int> div_by_3 = find_sequence(n / 3); if (div_by_3[0] < ans[0]) { ans.Clear(); ans.Add(div_by_3[0] + 1); ans.Add(n / 3); } } // Returns a tuple (a, b), where // a: Minimum steps to obtain x // from 1 b: Previous number return ans; } // Function that find the optimal // solution static List<int> find_solution(int n) { List<int> a = find_sequence(n); // Print the length Console.WriteLine(a[0]); List<int> sequence = new List<int>(); sequence.Add(n); // Exit condition for loop = -1 // when n has reached 1 while (a[1] != -1) { sequence.Add(a[1]); List<int> arr = find_sequence(a[1]); a.Insert(1, arr[1]); } // Return the sequence // in reverse order sequence.Reverse(); return sequence; } // Driver Code public static void Main(String []args) { // Given N int n = 5; // Function call List<int> res = find_solution(n); for(int i = 0; i < res.Count; i++) { Console.Write(res[i] + " "); } } } // This code is contributed by shikhasingrajput |
Javascript
<script> // JavaScript program to implement // the above approach function find_sequence(n) { // Base Case if (n == 1) return [1, -1]; // Recursive Call for n-1 var arr = find_sequence(n - 1); var ans = [arr[0] + 1, n - 1]; // Check if n is divisible by 2 if (n % 2 == 0) { var div_by_2 = find_sequence(n / 2); if (div_by_2[0] < ans[0]) ans = [div_by_2[0] + 1, n / 2]; } // Check if n is divisible by 3 if (n % 3 == 0) { var div_by_3 = find_sequence(n / 3); if (div_by_3[0] < ans[0]) var ans = [div_by_3[0] + 1, n / 3]; } // Returns a tuple (a, b), where // a: Minimum steps to obtain x from 1 // b: Previous number return ans; } // Function that find the optimal // solution function find_solution(n) { var a = find_sequence(n); // Print the length document.write( a[0] + "<br>"); var sequence = []; sequence.push(n); //Exit condition for loop = -1 //when n has reached 1 while (a[1] != -1) { sequence.push(a[1]); var arr = find_sequence(a[1]); a[1] = arr[1]; } // Return the sequence // in reverse order sequence.reverse(); return sequence; } // Driver Code // Given N var n = 5; // Function call var i = find_solution(n); i.forEach(j => { document.write(j + " "); }); </script> |
Output:
4 1 2 4 5
Time Complexity: T(N) = T(N-1) + T(N/2) + T(N/3), where N is given integer. This algorithm results in an exponential time complexity.
Auxiliary Space: O(1)
Recursion With Memoization Approach: The above approach can be optimized by memoizing the overlapping subproblems.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h> using namespace std; // Function to find the sequence // with given operations pair<int, int> find_sequence(int n, map<int, pair<int, int> >& map) { // Base Case if (n == 1) return make_pair(1, -1); // Check if the subproblem // is already computed or not if (map.find(n) != map.end()) return map[n]; // Recursive Call for n-1 pair<int, int> ans = make_pair( (find_sequence(n - 1, map).first + 1), n - 1); // Check if n is divisible by 2 if (n % 2 == 0) { pair<int, int> div_by_2 = find_sequence(n / 2, map); if (div_by_2.first < ans.first) ans = make_pair(div_by_2.first + 1, n / 2); } // Check if n is divisible by 3 if (n % 3 == 0) { pair<int, int> div_by_3 = find_sequence(n / 3, map); if (div_by_3.first < ans.first) ans = make_pair(div_by_3.first + 1, n / 3); } // Memoize map[n] = ans; // Returns a tuple (a, b), where // a: Minimum steps to obtain x from 1 // b: Previous state return ans; } // Function to check if a sequence can // be obtained with given operations vector<int> find_solution(int n) { // Stores the computed // subproblems map<int, pair<int, int> > map; pair<int, int> ans = find_sequence(n, map); // Return a sequence in // reverse order cout << ans.first << endl; vector<int> sequence; sequence.push_back(n); // If n has reached 1 while (ans.second != -1) { sequence.push_back(ans.second); ans = find_sequence(ans.second, map); } // Return sequence in reverse order reverse(sequence.begin(), sequence.end()); return sequence; } int main() { // Given N int n = 5; // Function Call vector<int> seq = find_solution(n); for (int i = 0; i < seq.size(); i++) cout << seq[i] << " "; } // This code is contributed by lokeshpotta20. |
Java
import java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.Map; public class Main { // Function to find the sequence // with given operations private static int[] findSequence(int n, Map<Integer, int[]> map) { // Base Case if (n == 1) return new int[] {1, -1}; // Check if the subproblem // is already computed or not if (map.containsKey(n)) return map.get(n); // Recursive Call for n-1 int[] ans = new int[] {findSequence(n - 1, map)[0] + 1, n - 1}; // Check if n is divisible by 2 if (n % 2 == 0) { int[] divBy2 = findSequence(n / 2, map); if (divBy2[0] < ans[0]) ans = new int[] {divBy2[0] + 1, n / 2}; } // Check if n is divisible by 3 if (n % 3 == 0) { int[] divBy3 = findSequence(n / 3, map); if (divBy3[0] < ans[0]) ans = new int[] {divBy3[0] + 1, n / 3}; } // Memoize map.put(n, ans); // Returns an array [a, b], where // a: Minimum steps to obtain x from 1 // b: Previous state return ans; } // Function to check if a sequence can // be obtained with given operations public static List<Integer> findSolution(int n) { // Stores the computed // subproblems Map<Integer, int[]> map = new HashMap<>(); int[] ans = findSequence(n, map); // Return a sequence in // reverse order System.out.println(ans[0]); List<Integer> sequence = new ArrayList<>(); sequence.add(n); // If n has reached 1 while (ans[1] != -1) { sequence.add(ans[1]); ans = findSequence(ans[1], map); } // Return sequence in reverse order java.util.Collections.reverse(sequence); return sequence; } public static void main(String[] args) { // Given N int n = 5; // Function Call List<Integer> seq = findSolution(n); for (int i = 0; i < seq.size(); i++) System.out.print(seq.get(i) + " "); } } |
Python3
# Python3 program to implement # the above approach # Function to find the sequence # with given operations def find_sequence(n, map): # Base Case if n == 1: return 1, -1 # Check if the subproblem # is already computed or not if n in map: return map[n] # Recursive Call for n-1 ans = (find_sequence(n - 1, map)[0]\ + 1, n - 1) # Check if n is divisible by 2 if n % 2 == 0: div_by_2 = find_sequence(n // 2, map) if div_by_2[0] < ans[0]: ans = (div_by_2[0] + 1, n // 2) # Check if n is divisible by 3 if n % 3 == 0: div_by_3 = find_sequence(n // 3, map) if div_by_3[0] < ans[0]: ans = (div_by_3[0] + 1, n // 3) # Memoize map[n] = ans # Returns a tuple (a, b), where # a: Minimum steps to obtain x from 1 # b: Previous state return ans # Function to check if a sequence can # be obtained with given operations def find_solution(n): # Stores the computed # subproblems map = {} a, b = find_sequence(n, map) # Return a sequence in # reverse order print(a) sequence = [] sequence.append(n) # If n has reached 1 while b != -1: sequence.append(b) _, b = find_sequence(b, map) # Return sequence in reverse order return sequence[::-1] # Driver Code # Given N n = 5 # Function Call print(*find_solution(n)) |
C#
using System; using System.Collections.Generic; class Program { static Dictionary<int, Tuple<int, int> > map = new Dictionary<int, Tuple<int, int> >(); // Function to find the sequence // with given operations static Tuple<int, int> FindSequence(int n) { // Base Case if (n == 1) return Tuple.Create(1, -1); // Check if the subproblem // is already computed or not if (map.ContainsKey(n)) return map[n]; // Recursive Call for n-1 Tuple<int, int> ans = Tuple.Create( (FindSequence(n - 1).Item1 + 1), n - 1); // Check if n is divisible by 2 if (n % 2 == 0) { Tuple<int, int> div_by_2 = FindSequence(n / 2); if (div_by_2.Item1 < ans.Item1) ans = Tuple.Create(div_by_2.Item1 + 1, n / 2); } // Check if n is divisible by 3 if (n % 3 == 0) { Tuple<int, int> div_by_3 = FindSequence(n / 3); if (div_by_3.Item1 < ans.Item1) ans = Tuple.Create(div_by_3.Item1 + 1, n / 3); } // Memoize map[n] = ans; // Returns a tuple (a, b), where // a: Minimum steps to obtain x from 1 // b: Previous state return ans; } // Function to check if a sequence can // be obtained with given operations static List<int> FindSolution(int n) { Tuple<int, int> ans = FindSequence(n); // Return a sequence in reverse order Console.WriteLine(ans.Item1); List<int> sequence = new List<int>(); sequence.Add(n); // If n has reached 1 while (ans.Item2 != -1) { sequence.Add(ans.Item2); ans = FindSequence(ans.Item2); } // Return sequence in reverse order sequence.Reverse(); return sequence; } static void Main(string[] args) { // Given N int n = 5; // Function Call List<int> seq = FindSolution(n); foreach(int num in seq) Console.Write(num + " "); } } // This code is contributed by divyansh2212 |
Javascript
// JavaScript implementation of the above approach // Function to find the sequence // with given operations function find_sequence(n, map) { // Base Case if (n === 1) { return [1, -1]; } // Check if the subproblem // is already computed or not if (map.hasOwnProperty(n)) { return map[n]; } // Recursive Call for n-1 let ans = [find_sequence(n - 1, map)[0] + 1, n - 1]; // Check if n is divisible by 2 if (n % 2 === 0) { let div_by_2 = find_sequence(n / 2, map); if (div_by_2[0] < ans[0]) { ans = [div_by_2[0] + 1, n / 2]; } } // Check if n is divisible by 3 if (n % 3 === 0) { let div_by_3 = find_sequence(n / 3, map); if (div_by_3[0] < ans[0]) { ans = [div_by_3[0] + 1, n / 3]; } } // Memoize map[n] = ans; // Returns a tuple [a, b], where // a: Minimum steps to obtain x from 1 // b: Previous state return ans; } // Function to check if a sequence can // be obtained with given operations function find_solution(n) { // Stores the computed // subproblems let map = {}; let [a, b] = find_sequence(n, map); // Return a sequence in // reverse order console.log(a); let sequence = []; sequence.push(n); // If n has reached 1 while (b !== -1) { sequence.push(b); [_, b] = find_sequence(b, map); } // Return sequence in reverse order return sequence.reverse(); } // Driver Code // Given N let n = 5; // Function Call console.log(...find_solution(n)); |
Output:
4 1 2 4 5
Time Complexity: O(N)
Auxiliary Space: O(N)
Iterative Dynamic Programming Approach: The above approach can be further optimized by using an iterative DP approach. Follow the steps below to solve the problem:
- Create an array dp[] to store the minimum length of sequence that is required to compute 1 to N by the three available operations.
- Once the dp[] array is computed, obtain the sequence by traversing the dp[] array from N to 1.
Below is the implementation of the above approach:
C++
// C++ program to implement // the above approach #include <bits/stdc++.h> using namespace std; // Function to generate // the minimum sequence void find_sequence(int n) { // Stores the values for the // minimum length of sequences int dp[n + 1]; memset(dp, 0, sizeof(dp)); // Base Case dp[1] = 1; // Loop to build up the dp[] // array from 1 to n for(int i = 1; i < n + 1; i++) { if (dp[i] != 0) { // If i + 1 is within limits if (i + 1 < n + 1 && (dp[i + 1] == 0 || dp[i + 1] > dp[i] + 1)) { // Update the state of i + 1 // in dp[] array to minimum dp[i + 1] = dp[i] + 1; } // If i * 2 is within limits if (i * 2 < n + 1 && (dp[i * 2] == 0 || dp[i * 2] > dp[i] + 1)) { // Update the state of i * 2 // in dp[] array to minimum dp[i * 2] = dp[i] + 1; } // If i * 3 is within limits if (i * 3 < n + 1 && (dp[i * 3] == 0 || dp[i * 3] > dp[i] + 1)) { // Update the state of i * 3 // in dp[] array to minimum dp[i * 3] = dp[i] + 1; } } } // Generate the sequence by // traversing the array vector<int> sequence; while (n >= 1) { // Append n to the sequence sequence.push_back(n); // If the value of n in dp // is obtained from n - 1: if (dp[n - 1] == dp[n] - 1) { n--; } // If the value of n in dp[] // is obtained from n / 2: else if (n % 2 == 0 && dp[(int)floor(n / 2)] == dp[n] - 1) { n = (int)floor(n / 2); } // If the value of n in dp[] // is obtained from n / 3: else if (n % 3 == 0 && dp[(int)floor(n / 3)] == dp[n] - 1) { n = (int)floor(n / 3); } } // Print the sequence // in reverse order reverse(sequence.begin(), sequence.end()); // Print the length of // the minimal sequence cout << sequence.size() << endl; for(int i = 0; i < sequence.size(); i++) { cout << sequence[i] << " "; } } // Driver code int main() { // Given Number N int n = 5; // Function Call find_sequence(n); return 0; } // This code is contributed by divyeshrabadiya07 |
Java
// Java program to implement // the above approach import java.io.*; import java.util.*; class GFG{ // Function to generate // the minimum sequence public static void find_sequence(int n) { // Stores the values for the // minimum length of sequences int[] dp = new int[n + 1]; Arrays.fill(dp, 0); // Base Case dp[1] = 1; // Loop to build up the dp[] // array from 1 to n for(int i = 1; i < n + 1; i++) { if (dp[i] != 0) { // If i + 1 is within limits if (i + 1 < n + 1 && (dp[i + 1] == 0 || dp[i + 1] > dp[i] + 1)) { // Update the state of i + 1 // in dp[] array to minimum dp[i + 1] = dp[i] + 1; } // If i * 2 is within limits if (i * 2 < n + 1 && (dp[i * 2] == 0 || dp[i * 2] > dp[i] + 1)) { // Update the state of i * 2 // in dp[] array to minimum dp[i * 2] = dp[i] + 1; } // If i * 3 is within limits if (i * 3 < n + 1 && (dp[i * 3] == 0 || dp[i * 3] > dp[i] + 1)) { // Update the state of i * 3 // in dp[] array to minimum dp[i * 3] = dp[i] + 1; } } } // Generate the sequence by // traversing the array List<Integer> sequence = new ArrayList<Integer>(); while (n >= 1) { // Append n to the sequence sequence.add(n); // If the value of n in dp // is obtained from n - 1: if (dp[n - 1] == dp[n] - 1) { n--; } // If the value of n in dp[] // is obtained from n / 2: else if (n % 2 == 0 && dp[(int)Math.floor(n / 2)] == dp[n] - 1) { n = (int)Math.floor(n / 2); } // If the value of n in dp[] // is obtained from n / 3: else if (n % 3 == 0 && dp[(int)Math.floor(n / 3)] == dp[n] - 1) { n = (int)Math.floor(n / 3); } } // Print the sequence // in reverse order Collections.reverse(sequence); // Print the length of // the minimal sequence System.out.println(sequence.size()); for(int i = 0; i < sequence.size(); i++) { System.out.print(sequence.get(i) + " "); } } // Driver Code public static void main (String[] args) { // Given Number N int n = 5; // Function Call find_sequence(n); } } // This code is contributed by avanitrachhadiya2155 |
Python3
# Python3 program to implement # the above approach # Function to generate # the minimum sequence def find_sequence(n): # Stores the values for the # minimum length of sequences dp = [0 for _ in range(n + 1)] # Base Case dp[1] = 1 # Loop to build up the dp[] # array from 1 to n for i in range(1, n + 1): if dp[i] != 0: # If i + 1 is within limits if i + 1 < n + 1 and (dp[i + 1] == 0 \ or dp[i + 1] > dp[i] + 1): # Update the state of i + 1 # in dp[] array to minimum dp[i + 1] = dp[i] + 1 # If i * 2 is within limits if i * 2 < n + 1 and (dp[i * 2] == 0 \ or dp[i * 2] > dp[i] + 1): # Update the state of i * 2 # in dp[] array to minimum dp[i * 2] = dp[i] + 1 # If i * 3 is within limits if i * 3 < n + 1 and (dp[i * 3] == 0 \ or dp[i * 3] > dp[i] + 1): # Update the state of i * 3 # in dp[] array to minimum dp[i * 3] = dp[i] + 1 # Generate the sequence by # traversing the array sequence = [] while n >= 1: # Append n to the sequence sequence.append(n) # If the value of n in dp # is obtained from n - 1: if dp[n - 1] == dp[n] - 1: n = n - 1 # If the value of n in dp[] # is obtained from n / 2: elif n % 2 == 0 \ and dp[n // 2] == dp[n] - 1: n = n // 2 # If the value of n in dp[] # is obtained from n / 3: elif n % 3 == 0 \ and dp[n // 3] == dp[n] - 1: n = n // 3 # Return the sequence # in reverse order return sequence[::-1] # Driver Code # Given Number N n = 5 # Function Call sequence = find_sequence(n) # Print the length of # the minimal sequence print(len(sequence)) # Print the sequence print(*sequence) |
C#
// C# program to implement // the above approach using System; using System.Collections.Generic; class GFG { // Function to generate // the minimum sequence public static void find_sequence(int n) { // Stores the values for the // minimum length of sequences int[] dp = new int[n + 1]; Array.Fill(dp, 0); // Base Case dp[1] = 1; // Loop to build up the dp[] // array from 1 to n for(int i = 1; i < n + 1; i++) { if(dp[i] != 0) { // If i + 1 is within limits if(i + 1 < n + 1 && (dp[i + 1] == 0 || dp[i + 1] > dp[i] + 1)) { // Update the state of i + 1 // in dp[] array to minimum dp[i + 1] = dp[i] + 1; } // If i * 2 is within limits if(i * 2 < n + 1 && (dp[i * 2] == 0 || dp[i * 2] > dp[i] + 1)) { // Update the state of i * 2 // in dp[] array to minimum dp[i * 2] = dp[i] + 1; } // If i * 3 is within limits if(i * 3 < n + 1 && (dp[i * 3] == 0 || dp[i * 3] > dp[i] + 1)) { // Update the state of i * 3 // in dp[] array to minimum dp[i * 3] = dp[i] + 1; } } } // Generate the sequence by // traversing the array List<int> sequence = new List<int>(); while(n >= 1) { // Append n to the sequence sequence.Add(n); // If the value of n in dp // is obtained from n - 1: if(dp[n - 1] == dp[n] - 1) { n--; } // If the value of n in dp[] // is obtained from n / 2: else if(n % 2 == 0 && dp[(int)Math.Floor((decimal)n / 2)] == dp[n] - 1) { n = (int)Math.Floor((decimal)n / 2); } // If the value of n in dp[] // is obtained from n / 3: else if(n % 3 == 0 && dp[(int)Math.Floor((decimal)n / 3)] == dp[n] - 1) { n = (int)Math.Floor((decimal)n / 3); } } // Print the sequence // in reverse order sequence.Reverse(); // Print the length of // the minimal sequence Console.WriteLine(sequence.Count); for(int i = 0; i < sequence.Count; i++) { Console.Write(sequence[i] + " "); } } // Driver Code static public void Main () { // Given Number N int n = 5; // Function Call find_sequence(n); } } // This code is contributed by rag2127 |
Javascript
<script> // Javascript program to implement // the above approach // Function to generate // the minimum sequence function find_sequence(n) { // Stores the values for the // minimum length of sequences let dp = new Array(n + 1); for(let i=0;i<n+1;i++) { dp[i]=0; } // Base Case dp[1] = 1; // Loop to build up the dp[] // array from 1 to n for(let i = 1; i < n + 1; i++) { if (dp[i] != 0) { // If i + 1 is within limits if (i + 1 < n + 1 && (dp[i + 1] == 0 || dp[i + 1] > dp[i] + 1)) { // Update the state of i + 1 // in dp[] array to minimum dp[i + 1] = dp[i] + 1; } // If i * 2 is within limits if (i * 2 < n + 1 && (dp[i * 2] == 0 || dp[i * 2] > dp[i] + 1)) { // Update the state of i * 2 // in dp[] array to minimum dp[i * 2] = dp[i] + 1; } // If i * 3 is within limits if (i * 3 < n + 1 && (dp[i * 3] == 0 || dp[i * 3] > dp[i] + 1)) { // Update the state of i * 3 // in dp[] array to minimum dp[i * 3] = dp[i] + 1; } } } // Generate the sequence by // traversing the array let sequence = []; while (n >= 1) { // Append n to the sequence sequence.push(n); // If the value of n in dp // is obtained from n - 1: if (dp[n - 1] == dp[n] - 1) { n--; } // If the value of n in dp[] // is obtained from n / 2: else if (n % 2 == 0 && dp[(Math.floor(n / 2))] == dp[n] - 1) { n = Math.floor(n / 2); } // If the value of n in dp[] // is obtained from n / 3: else if (n % 3 == 0 && dp[(Math.floor(n / 3))] == dp[n] - 1) { n = Math.floor(n / 3); } } // Print the sequence // in reverse order sequence.reverse(); // Print the length of // the minimal sequence document.write(sequence.length+"<br>"); for(let i = 0; i < sequence.length; i++) { document.write(sequence[i] + " "); } } // Driver Code let n = 5; // Function Call find_sequence(n); // This code is contributed by unknown2108 </script> |
Output:
4 1 3 4 5
Time Complexity: O(N)
Auxiliary Space: O(N)
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!
