Horje
Maximum Sequence Length | Collatz Conjecture

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 approach
using 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)


 


Reffered: https://www.geeksforgeeks.org

Algorithms

Related
Check if the rows of a binary matrix can be made unique by removing a single column Check if the rows of a binary matrix can be made unique by removing a single column
Count of triples (A, B, C) where A*C is greater than B*B Count of triples (A, B, C) where A*C is greater than B*B
Maximum perimeter of a square in a 2D grid Maximum perimeter of a square in a 2D grid
Find if a degree sequence can form a simple graph | Havel-Hakimi Algorithm Find if a degree sequence can form a simple graph | Havel-Hakimi Algorithm
Replace elements with absolute difference of smallest element on left and largest element on right Replace elements with absolute difference of smallest element on left and largest element on right

Type:
 Geek
Category:
 Coding
Sub Category:
 Tutorial
Uploaded by:
 Admin
Views:
 11



 

Horje