• Home
  • Subscribe
  • Contribute Us
    • Share Your Interview Experience
  • Contact Us
  • About
    • About CSEstack
    • Campus Ambassador
  • Forum & Discus
  • Tools for Geek
  • LeaderBoard
CSEstack

What do you want to Learn Today?

  • Programming
    • Tutorial- C/C++
    • Tutorial- Django
    • Tutorial- Git
    • Tutorial- HTML & CSS
    • Tutorial- Java
    • Tutorial- MySQL
    • Tutorial- Python
    • Competitive Coding Challenges
  • CSE Subject
    • (CD) Compiler Design
    • (CN) Computer Network
    • (COA) Computer Organization & Architecture
    • (DBMS) Database Management System
    • (DS) Data Structure
    • (OS) Operating System
    • (ToA) Theory of Automata
    • (WT) Web Technology
  • Interview Questions
    • Interview Questions- Company Wise
    • Interview Questions- Coding Round
    • Interview Questions- Python
    • Interview Questions- REST API
    • Interview Questions- Web Scraping
    • Interview Questions- HR Round
    • Aptitude Preparation Guide
  • GATE 2022
  • Linux
  • Trend
    • Full Stack Development
    • Artificial Intelligence (AI)
    • BigData
    • Cloud Computing
    • Machine Learning (ML)
  • Write for Us
    • Submit Article
    • Submit Source Code or Program
    • Share Your Interview Experience
  • Tools
    • IDE
    • CV Builder
    • Other Tools …
  • Jobs

[Solved] Hailstone Sequence in Python (With or Without Recursion)

Aniruddha Chaudhari/14175/0
CodePython

In this tutorial, you will learn what is hailstone sequence, how to write a Python program to find the hailstone sequence with and without recursion.

Let’s start with the basic algorithm to find the hailstone sequence.

Table of Contents

  • Hailstone Sequence Algorithm
  • Hailstone Sequence Python Program using while Loop
  • Hailstone Sequence Python Program with Recursion
  • Find the Length of the Hailstone Sequence
  • Find the Maximum Length of Hailstone Sequence for the Range of Given Numbers
  • Plot Hailstone Sequence in Graph

Hailstone Sequence Algorithm

  • Take a number (says ‘n’) as an input.
  • Print the value of ‘n’.
  • while n != 1
    a) Print the value of ‘n’.
    b) If ‘n’ is odd, calculate the next number as n*3+1.
    c) If ‘n’ is even, calculate the next number as n/2.

Example:

Input : 10
Output (Hailstone Sequence): 10 -> 5 -> 16 -> 8 -> 4 -> 2 ->1
Input : 17
Output (Hailstone Sequence): 17 -> 52 -> 26 -> 13 -> 40 -> 20 ->10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1

If you plot the graph for hailstone sequences for 10, 11, 12, 13, 14 and 15, it looks like below.

hailstone sequence graph using matplotlib

(I will share the code for piloting the graph at end of this tutorial.)

Hailstone Sequence Python Program using while Loop

We are using Python while loop to solve this problem.

Python Program:

def hailstone_seq(start):
  list_out = []
  while start > 1:
    list_out.append(int(start))
    if start%2 == 1:
      start = int(start*3+1)
    else:
      start = int(start/2)
  list_out.append(1)
  return list_out
 
if __name__ == "__main__":
  n = input("Enter the number:")
  if n.isnumeric():
    n = int(n)
    list_out = hailstone_seq(n)
    print("Hailstone Sequence: ", list_out)
  else:
    print("Invalid input.")

Output:

Enter the number: 10
Hailstone Sequence: [10, 5, 16, 8, 4, 2, 1]

When you take the user input, check if the user input value is numeric or not. You can check it with the isnumeric() string method.

Other parts of the code are self-explanatory.

Hailstone Sequence Python Program with Recursion

Hope you are familiar with the recursion programming concepts.

Python Program:

def hailstone_seq_rec(start, list_out=[]):

  #base condition
  if start == 1:
    list_out.append(1)
    return list_out

  list_out.append(int(start))

  if start%2 == 1:
    return hailstone_seq_rec(start*3+1, list_out)
  else:
    return hailstone_seq_rec(start/2, list_out)

if __name__ == "__main__":
  n = input("Enter the number:")
  if n.isnumeric():
    n = int(n)
    list_out = hailstone_seq_rec(n)
    print("Hailstone Sequence: ", list_out)
  else:
    print("Invalid input.")

Output:

Enter the number: 15
Hailstone Sequence: [15, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1]

Find the Length of the Hailstone Sequence

You can find the length of the hailstone sequence simply by finding the length of the list having all the hailstone sequence numbers.

If our aim is to find only the length of the sequence, it is not efficient to store all hailstone sequence values. Instead of that, we calculate the length.

The same code we used to find the hailstone sequence can be used to calculate the length with a few lines of changes in code.

Python Program: Without using recursion (while loop)

def hailstone_seq_len(start):
  len_seq = 0

  while start > 1:
    len_seq = len_seq+1
    if start%2 == 1:
      start = int(start*3+1)
    else:
      start = int(start/2)

  return len_seq+1
 
if __name__ == "__main__":
  n = input("Enter the number:")
  if n.isnumeric():
    n = int(n)
    len_seq = hailstone_seq_len(n)
    print("Length of Hailstone Sequence = ", len_seq)
  else:
    print("Invalid input.")

Output:

Enter the number:10
Length of Hailstone Sequence = 7

Python Program: Using recursion

def hailstone_seq_rec_len(start, len_seq=0):

  #base condition
  if start == 1:
    return len_seq+1

  len_seq =len_seq+1

  if start%2 == 1:
    return hailstone_seq_rec_len(start*3+1, len_seq)
  else:
    return hailstone_seq_rec_len(start/2, len_seq)

if __name__ == "__main__":
  n = input("Enter the number:")
  if n.isnumeric():
    n = int(n)
    len_seq = hailstone_seq_rec_len(n)
    print("Length of the hailstone sequence = ", len_seq)
  else:
    print("Invalid input.")

Output:

Enter the number:15
Length of the hailstone sequence = 18

Find the Maximum Length of Hailstone Sequence for the Range of Given Numbers

Problem statement: Write a program hailstones.py that prints all hailstone sequences with starting numbers from 1 to n and prints the number that has the longest hailstone sequence.

You have to find the seed having the maximum length of the hailstone sequence for the hailstone sequences for all the numbers in the range of given numbers.

Algorithm:

  • Take two numbers as input (says a, b).
  • Find a hailstone sequence length of all the values ranging from a to b.
  • Return maximum length out of all the lengths of hailstone sequences.

Python Program:

def hailstone_seq_len(start):
  len_seq = 0

  while start > 1:
    len_seq = len_seq+1
    if start%2 == 1:
      start = int(start*3+1)
    else:
      start = int(start/2)

  return len_seq+1
 
if __name__ == "__main__":
  a = input("Enter the number a:")
  b = input("Enter the number b:")
  max_len = 0
  max_seed = 0
  if a.isnumeric() and b.isnumeric():
    a = int(a)
    b = int(b)
    for i in range(a, b+1):
      len_temp = hailstone_seq_len(i)
      if len_temp > max_len:
        max_len = len_temp
        max_seed = i
    print("Max length of the Hailstone Sequence is %d for seed %d." %(max_len, max_seed))

  else:
    print("Invalid input.")

Output:

Enter the number a: 10
Enter the number b: 15
Max length of the Hailstone Sequence is 18 for seed 14.

When I attended an interview with NVIDIA, they asked me to optimize it further.

We can use a dynamic programming approach to optimize this problem.

Let’s look at the hailstone sequence for 10 and 11.

[10, 5, 16, 8, 4, 2, 1] 
[11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]

Here the total iteration to calculate hailstone sequence length will be 22.

7 (length of hailstone sequence for 10) + 15 (length of hailstone sequence for 11)= 22

How can we optimize it?

Observe the sequence for 10 and 11. The hailstone sequence for 10 is a subset of the hailstone sequence for 11.

  • Calculate the length of the hailstone sequence for 10. (The number of iterations required is 7).
  • Store the length in the hailstone sequence for 10 in the dictionary (says ‘hs_len_dict’).
  • Calculate the length of the hailstone sequence for 11. This can be calculated by finding the light of the hailstone sequence to 10 (The number of Iteration requires is 8) plus the length of the hailstone sequence for 10 (from the dictionary).
  • So the total iterations required for calculating the length of the hailstone sequence for 10 and 11 is 15 (7+8).

With this optimization, we have saved the number of iterations from 22 to 15.

Python Program with Optimization:

hs_len_dict = {}
 
itr = 0
 
def hailstone_seq_len(start):
  global itr
  len_seq = 0
  
  while start > 1:
    itr = itr+1

    if start in hs_len_dict:
      return hs_len_dict[start]+len_seq
  
    len_seq = len_seq+1
    if start%2 == 1:
      start = int(start*3+1)
    else:
      start = int(start/2)
  
  return len_seq+1
  
if __name__ == "__main__":
  a = input("Enter the number a:")
  b = input("Enter the number b:")
  max_len = 0
  max_seed = 0
  if a.isnumeric() and b.isnumeric():
    a = int(a)
    b = int(b)
    for i in range(a, b+1):
      len_temp = hailstone_seq_len(i)
      hs_len_dict[i] = len_temp
        
      if len_temp > max_len:
        max_len = len_temp
        max_seed = i
    print("Max lenght of the Hailstone Sequence is %d for seed %d" %(max_len, max_seed))
  
  else:
    print("Invalid input.")

  print("Number of iteration: ", itr)

Output:

The final output of the optimized code will be the same, but the process is optimized. The number of iterations required has dropped from 72 to 39.

Enter the number a:
Enter the number b:
Max length of the Hailstone Sequence is 18 for seed 14
Number of iteration: 39

You can also further optimize this program by calculating the square root of the number. (Hint: If the given number is a square of two, the length of the Hailstone Sequence is the square root of that number.)

Plot Hailstone Sequence in Graph

We are using matplotlob library for plotting the graph. It is one of the most used Data Science Python libraries used for graph plots.

If you don’t have matplotlib library installed, you can install it using pip tool. Here is the command.

pip install matplotlib

Let’s plot the graph for hailstone sequences for 10 to 15.

Python Program:

from matplotlib import pyplot as plt
 
def hailstone_seq(start):
  list_out = []
  while start > 1:
    list_out.append(int(start))
    if start%2 == 1:
      start = int(start*3+1)
    else:
      start = int(start/2)
  list_out.append(1)
  return list_out
 
if __name__ == "__main__":
  a = 10
  b = 15
  for i in range(a, b+1):
    list_out = hailstone_seq(i)
    plt.plot(list_out, label='HS for %d'%i)
    plt.legend()
  plt.show()

Output:

Hailstone Sequence in Python is a very interesting and common problem of sequencing.

This problem has been asked in many interviews for different companies.

If you have any questions regarding the hailstone sequence problem, let’s discuss it in the comment.

Python Interview Questions eBook

coding challenge
Aniruddha Chaudhari
I am complete Python Nut, love Linux and vim as an editor. I hold a Master of Computer Science from NIT Trichy. I dabble in C/C++, Java too. I keep sharing my coding knowledge and my own experience on CSEstack.org portal.

Your name can also be listed here. Got a tip? Submit it here to become an CSEstack author.

Leave a Reply Cancel reply

Why?

Why Competitive Programming Important?

Coding Challenges for Practice

  1. Count Common Factor
  2. Does it Divide
  3. Sum of Sub Arrays
  4. Pair of Desired Sum
  5. Remove Duplicate Char from String
  6. Sort String by Char Freq (Python)
  7. Sort String by Char Freq (Java)
  8. Split Array into Equal Sum Subarray
  9. Validate IP Address
  10. Validate PAN Card Number
  11. Validate Sudoku
  12. Sort Circular Rotated Array
  13. String Permutations
  14. Min Arrow to Burst Bubbles
  15. Min Cost to Paint All Houses [Amazon]
  16. HourGlass with Max Sum
  17. Max Profit by Buying/Selling Stocks
  18. Hailstone Sequence
  19. Reverse String without affecting Special Characters
  20. Secure Conversation by Encry/Decry
  21. Special Elements in Matrix
  22. Next Greater No with Same set of Digits
  23. Smallest Subarray with Sum Greater than Given Number
  24. Group Anagrams
  25. Find Duplicates in Array in O(n)
  26. Find Two Unique Numbers from Array in O(n)
  27. Number Patterns & Finding Smallest Number
  28. First Unique Element in a Stream
  29. Flip Equivalent Binary Trees [TeachMint]
  30. Minimum Cost of Merging Files [Amazon]
  31. Minimum Distance for Truck to Deliver Order [Amazon]
  32. Longest Sequence of URLs
  33. Order Task for Given Dependencies
  34. Design Music Player
  35. Multilevel Parking System Design
  36. Minimum Coins Required
  37. Max Sum Subarray
  38. Max Avg Sum of Two Subsequences
  39. Merge Overlapping Intervals
  40. Longest Balanced Substring
  41. Longest Path in a Weighted Tree
  42. Generate Balanced Parentheses
  43. PostOrder Traversal Without Recursion

© 2022 – CSEstack.org. All Rights Reserved.

  • Home
  • Subscribe
  • Contribute Us
    • Share Your Interview Experience
  • Contact Us
  • About
    • About CSEstack
    • Campus Ambassador
  • Forum & Discus
  • Tools for Geek
  • LeaderBoard