Lychrel Number is a natural number that cannot form a palindrome through the iterative process of repeatedly reversing its digits and adding the resulting numbers. The process is sometimes called the 196-algorithm, after the most famous number associated with the process.
The first few numbers not known to produce palindromes when applying the 196-algorithm (i.e., a reverse-then-add sequence) are sometimes known as Lychrel numbers.
Examples:
Input : 56 Output : 56 is lychrel : false Explanation : 56 becomes palindromic after one iteration : 56 + 65 = 121 Input : 196 Output : 196 is lychrel : true Explanation : 196 becomes palindromic after 19 iterations : 196 + 691 = 887 887 + 788 = 1675 1675 + 5761 = 7436 7436 + 6347 = 13783 13783 + 38731 = 52514 .... 16403234045 + 54043230461 70446464506 + 60546464407
The task is to find if a given number is Lychrel with a given limit on the number of iterations.
1. Iterate given number of times
1. Add number to it's reverse
2. If
the newly formed number is palindrome
then
return false // Number is not lychrel.
2. return true // Number is lychrel
Following are the steps to solve this problem :
- Create functions to check for palindromes and reverse numbers.
- Define a function that iterates a certain amount of times while looking for Lychrel numbers.
- Initialize a long integer variable with the number to be checked in the main function.
- Call the isLychrel function and store the result.
- Print the input number and the isLychrel function’s result.
- Run the program while changing the input numbers.
Below is the implementation of the above approach :
C++
// C++ Program to check whether the given number// is Lychrel Number or not with given limit// on number of iterations.#include<iostream>using namespace std;long reverse(long);bool isPalindrome(long);// Max Iterationsstatic int MAX_ITERATIONS = 20;// Function to check whether number is // Lychrel Numberstring isLychrel(long number){ for (int i = 0; i < MAX_ITERATIONS; i++) { number = number + reverse(number); if (isPalindrome(number)) return "false"; } return "true";}// Function to check whether the number is// Palindromebool isPalindrome(long number){ return number == reverse(number);}// Function to reverse the numberlong reverse(long number){ long reverse = 0; while (number > 0) { long remainder = number % 10; reverse = (reverse * 10) + remainder; number = number / 10; } return reverse;}// Driver programint main(){ long number = 295; cout<<number << " is lychrel? " << isLychrel(number);}// This code is contributed by Smitha |
Java
// Java Program to check whether the given number// is Lychrel Number or not with given limit// on number of iterations.import java.io.*;public class LychrelNumberTest{ // Max Iterations private static int MAX_ITERATIONS = 20; // Function to check whether number is Lychrel Number private static boolean isLychrel(long number) { for (int i = 0; i < MAX_ITERATIONS; i++) { number = number + reverse(number); if (isPalindrome(number)) return false; } return true; } // Function to check whether the number is Palindrome private static boolean isPalindrome(final long number) { return number == reverse(number); } // Function to reverse the number private static long reverse(long number) { long reverse = 0; while (number > 0) { long remainder = number % 10; reverse = (reverse * 10) + remainder; number = number / 10; } return reverse; } // driver program public static void main(String[] args) { long number = 295; System.out.println(number + " is lychrel? " + isLychrel(number)); }} |
Python3
# Python3 Program to check whether the given number # is Lychrel Number or not with given limit # on number of iterations. # Max Iterations MAX_ITERATIONS = 20; # Function to check whether number is # Lychrel Number def isLychrel(number): for i in range(MAX_ITERATIONS): number = number + reverse(number); if (isPalindrome(number)): return "false"; return "true"; # Function to check whether the number # is Palindrome def isPalindrome(number): return number == reverse(number); # Function to reverse the number def reverse(number): reverse = 0; while (number > 0): remainder = number % 10; reverse = (reverse * 10) + remainder; number = int(number / 10); return reverse; # Driver Codenumber = 295; print(number," is lychrel? ",isLychrel(number)); # This code is contributed by mits |
C#
// C# Program to check whether the given number// is Lychrel Number or not with given limit// on number of iterations.using System;class GFG{ // Max Iterations private static int MAX_ITERATIONS = 20; // Function to check whether number is Lychrel Number private static bool isLychrel(long number) { for (int i = 0; i < MAX_ITERATIONS; i++) { number = number + reverse(number); if (isPalindrome(number)) return false; } return true; } // Function to check whether the number is Palindrome private static bool isPalindrome( long number) { return number == reverse(number); } // Function to reverse the number private static long reverse(long number) { long reverse = 0; while (number > 0) { long remainder = number % 10; reverse = (reverse * 10) + remainder; number = number / 10; } return reverse; } // Driver program public static void Main() { long number = 295; Console.Write(number + " is lychrel? " + isLychrel(number)); }}// This code is contributed by vt_m. |
PHP
<?php// PHP Program to check whether the given number // is Lychrel Number or not with given limit // on number of iterations. // Max Iterations $MAX_ITERATIONS = 20; // Function to check whether number is // Lychrel Number function isLychrel($number) { global $MAX_ITERATIONS; for ($i = 0; $i < $MAX_ITERATIONS; $i++) { $number = $number + reverse($number); if (isPalindrome($number)) return "false"; } return "true"; } // Function to check whether the number // is Palindrome function isPalindrome($number) { return $number == reverse($number); } // Function to reverse the number function reverse($number) { $reverse = 0; while ($number > 0) { $remainder = $number % 10; $reverse = ($reverse * 10) + $remainder; $number = (int)($number / 10); } return $reverse; } // Driver Code$number = 295; echo $number . " is lychrel? " . isLychrel($number); // This code is contributed by mits ?> |
Javascript
<script>// Javascript Program to check // whether the given number is Lychrel // Number or not with given limit// on number of iterations.// Max Iterationsvar MAX_ITERATIONS = 20;// Function to check whether// number is Lychrel Numberfunction isLychrel(number){ for (var i = 0; i < MAX_ITERATIONS; i++) { number = number + reverse(number); if (isPalindrome(number)) return false; } return true;}// Function to check whether the // number is Palindromefunction isPalindrome(number){ return number == reverse(number);}// Function to reverse the numberfunction reverse(number){ var reverse = 0; while (number > 0) { var remainder = number % 10; reverse = (reverse * 10) + remainder; number = parseInt(number / 10); } return reverse;}// driver programvar number = 295;document.write(number + " is lychrel ? " + isLychrel(number));// This code contributed by shikhasingrajput </script> |
Output:
295 is lychrel ? true
Complexity Analysis :
- Time Complexity : O(log N) ; it is because time complexity of the reverse and isPalindrome functions is O(log N), where N is the number of digits in the input number
- Auxiliary Space : O(1) ; this is constant since it does not depend on the input size
This article is contributed by Pramod Kumar. If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
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!
