Given an integer N. The task is to find the number in the range from 1 to N-1 which is having the maximum number of terms in its Collatz Sequence and the number of terms in the sequence.
The collatz sequence of a number N is defined as:
- If N is Odd then change N to 3*N + 1.
- If N is Even then change N to N / 2.
For example let us have a look at the sequence when N = 13:
13 -> 40 -> 20 -> 10 -> 5 > 16 -> 8 -> 4 -> 2 -> 1
Examples:
Input: 10
Output: (9, 20)
9 has 20 terms in its Collatz sequence
Input: 50
Output: (27, 112)
27 has 112 terms
Approach:
As in the above example discussed for N = 13, collatz sequence for N = 13 and N = 40 have similar terms except one, that ensures there may be an involvement of dynamic programming to store the answer for subproblems and reuse it.
But here normal memoization will not work because at one step we are either making a number large from itself ( in above example N = 13 is depending upon the solution of N = 40 ) or dividing by 2 ( N = 40 solution depends upon the solution of N = 20 ).
So instead of using a dp array we will use a Map/ dictionary data structure to store the solution of subproblems and will perform the normal operation as discussed in the collatz sequence.
Below is the implementation of the above approach:
C++
#include<bits/stdc++.h>using namespace std;int collatzLenUtil(int n, unordered_map<int,int>&collLenMap){ // If value already // computed, return it if(collLenMap.find(n) != collLenMap.end()) return collLenMap[n]; // Base case if(n == 1) collLenMap[n] = 1; // Even case else if(n % 2 == 0){ collLenMap[n] = 1 + collatzLenUtil(n/2 , collLenMap); } // Odd case else{ collLenMap[n] = 1 + collatzLenUtil(3 * n + 1, collLenMap); } return collLenMap[n];}pair<int,int> collatzLen(int n){ // Declare empty Map / Dict // to store collatz lengths unordered_map<int,int>collLenMap; collatzLenUtil(n, collLenMap); // Initialise ans and // its collatz length int num = -1, l = 0; for(int i=1;i<n;i++){ // If value not already computed, // pass Dict to Helper function // and calculate and store value if(collLenMap.find(i)==collLenMap.end()) collatzLenUtil(i, collLenMap); int cLen = collLenMap[i]; if(l < cLen){ l = cLen; num = i; } } // Return ans and // its collatz length return {num, l};}int main(){ cout<<"("<<collatzLen(10).first<<", "<<collatzLen(10).second<<")"<<endl;}// This code is contributed by shinjanpatra |
Java
/*package whatever //do not write package name here */import java.io.*;import java.util.*;class GFG {static int collatzLenUtil(int n, HashMap<Integer,Integer>collLenMap){ // If value already // computed, return it if(collLenMap.containsKey(n)) return collLenMap.get(n); // Base case if(n == 1) collLenMap.put(n , 1); // Even case else if(n % 2 == 0){ collLenMap.put(n , 1 + collatzLenUtil(n/2 , collLenMap)); } // Odd case else{ collLenMap.put(n , 1 + collatzLenUtil(3 * n + 1, collLenMap)); } return collLenMap.get(n);} static int[] collatzLen(int n){ // Declare empty Map / Dict // to store collatz lengths HashMap<Integer,Integer> collLenMap = new HashMap<>(); collatzLenUtil(n, collLenMap); // Initialise ans and // its collatz length int num = -1, l = 0; for(int i=1;i<n;i++){ // If value not already computed, // pass Dict to Helper function // and calculate and store value if(collLenMap.containsKey(i)==false) collatzLenUtil(i, collLenMap); int cLen = collLenMap.get(i); if(l < cLen){ l = cLen; num = i; } } // Return ans and // its collatz length int res[] = {num, l}; return res;} /* Driver program to test above function*/public static void main(String args[]){ System.out.println("(" + collatzLen(10)[0]+", "+collatzLen(10)[1] + ")");}}// This code is contributed by shinjanpatra |
Python3
def collatzLenUtil(n, collLenMap): # If value already # computed, return it if n in collLenMap: return collLenMap[n] # Base case if(n == 1): collLenMap[n] = 1 # Even case elif(n % 2 == 0): collLenMap[n] \ = 1 \ + collatzLenUtil(n//2, collLenMap) # Odd case else: collLenMap[n] \ = 1 \ + collatzLenUtil(3 * n + 1, collLenMap) return collLenMap[n]def collatzLen(n): # Declare empty Map / Dict # to store collatz lengths collLenMap = {} collatzLenUtil(n, collLenMap) # Initialise ans and # its collatz length num, l =-1, 0 for i in range(1, n): # If value not already computed, # pass Dict to Helper function # and calculate and store value if i not in collLenMap: collatzLenUtil(i, collLenMap) cLen = collLenMap[i] if l < cLen: l = cLen num = i # Return ans and # its collatz length return (num, l)print(collatzLen(10)) |
C#
// C# code to implement the approachusing System;using System.Collections.Generic;class GFG { static int collatzLenUtil(int n, Dictionary<int, int> collLenMap) { // If value already // comAdded, return it if (collLenMap.ContainsKey(n)) return collLenMap[n]; // Base case if (n == 1) collLenMap.Add(n, 1); // Even case else if (n % 2 == 0) { collLenMap.Add( n, 1 + collatzLenUtil(n / 2, collLenMap)); } // Odd case else { collLenMap.Add( n, 1 + collatzLenUtil(3 * n + 1, collLenMap)); } return collLenMap[n]; } static int[] collatzLen(int n) { // Declare empty Map / Dict // to store collatz lengths Dictionary<int, int> collLenMap = new Dictionary<int, int>(); collatzLenUtil(n, collLenMap); // Initialise ans and // its collatz length int num = -1, l = 0; for (int i = 1; i < n; i++) { // If value not already comAdded, // pass Dict to Helper function // and calculate and store value if (collLenMap.ContainsKey(i) == false) collatzLenUtil(i, collLenMap); int cLen = collLenMap[i]; if (l < cLen) { l = cLen; num = i; } } // Return ans and // its collatz length int[] res = { num, l }; return res; } /* Driver program to test above function*/ public static void Main(string[] args) { Console.WriteLine("(" + collatzLen(10)[0] + ", " + collatzLen(10)[1] + ")"); }}// This code is contributed by phasing17 |
Javascript
<script>function collatzLenUtil(n, collLenMap){ // If value already // computed, return it if(collLenMap.has(n)) return collLenMap.get(n) // Base case if(n == 1) collLenMap.set(n, 1) // Even case else if(n % 2 == 0){ collLenMap.set(n , 1 + collatzLenUtil(Math.floor(n/2) , collLenMap)) } // Odd case else{ collLenMap.set(n , 1 + collatzLenUtil(3 * n + 1, collLenMap)) } return collLenMap.get(n);}function collatzLen(n){ // Declare empty Map / Dict // to store collatz lengths let collLenMap = new Map() collatzLenUtil(n, collLenMap) // Initialise ans and // its collatz length let num = -1, l = 0 for(let i=1;i<n;i++){ // If value not already computed, // pass Dict to Helper function // and calculate and store value if(collLenMap.has(i)==false) collatzLenUtil(i, collLenMap) let cLen = collLenMap.get(i) if(l < cLen){ l = cLen num = i } } // Return ans and // its collatz length return [num, l]}document.write(collatzLen(10))// This code is contributed by shinjanpatra</script> |
Output:
(9, 20)
Time Complexity: O(n*log(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!
