A number is called happy if it leads to 1 after a sequence of steps wherein each step number is replaced by the sum of squares of its digit that is if we start with Happy Number and keep replacing it with digits square sum, we reach 1.
Examples :
Input: n = 19 Output: True 19 is Happy Number, 1^2 + 9^2 = 82 8^2 + 2^2 = 68 6^2 + 8^2 = 100 1^2 + 0^2 + 0^2 = 1 As we reached to 1, 19 is a Happy Number. Input: n = 20 Output: False
A number will not be a Happy Number when it makes a loop in its sequence that is it touches a number in sequence which already been touched. So to check whether a number is happy or not, we can keep a set, if the same number occurs again we flag result as not happy. A simple function on the above approach can be written as below –
C++
// method return true if n is Happy Number// numSquareSum method is given in below detailed code snippetint isHappyNumber(int n){ set<int> st; while (1) { n = numSquareSum(n); if (n == 1) return true; if (st.find(n) != st.end()) return false; st.insert(n); }} |
Java
// method return true if n is Happy Number// numSquareSum method is given in below detailed code snippetstatic boolean isHappyNumber(int n) { HashSet<Integer> st = new HashSet<>(); while (true) { n = numSquareSum(n); if (n == 1) return true; if (st.contains(n)) return false; st.add(n); }}// This code is contributed by Princi Singh |
C#
// Method return true if n is Happy Number// numSquareSum method is given in below// detailed code snippetstatic int isHappyNumber(int n){ HashSet<int> st = new HashSet<>(); while (1) { n = numSquareSum(n); if (n == 1) return true; if (st.Contains(n)) return false; st.Add(n); }}// This code is contributed by 29AjayKumar |
Javascript
<script>// method return true if n is Happy Number// numSquareSum method is given in below detailed code snippet let st = new Set(); while (1) { n = numSquareSum(n); if (n == 1) return true; if (st.has(n)) return false; st.add(n); }}//This code is contributed by Mayank Tyagi</script> |
Python3
# method return true if n is Happy Number# numSquareSum method is given in below detailed code snippetdef isHappyNumber(n): st=set() while (1): n = numSquareSum(n) if (n == 1): return True if n not in st: return False st.insert(n) |
Complexity Analysis:
Time Complexity: O(n*log(n)).
Auxiliary Space: O(n) since using extra set for storage
We can solve this problem without using extra space and that technique can be used in some other similar problems also. If we treat every number as a node and replacement by square sum digit as a link, then this problem is same as finding a loop in a linklist :
So as a proposed solution from the above link, we will keep two numbers slow and fast both initialize from a given number, slow is replaced one step at a time and fast is replaced two steps at a time. If they meet at 1, then the given number is Happy Number otherwise not.
C++
// C++ program to check a number is a Happy number or not#include <bits/stdc++.h>using namespace std;// Utility method to return sum of square of digit of nint numSquareSum(int n){ int squareSum = 0; while (n) { squareSum += (n % 10) * (n % 10); n /= 10; } return squareSum;}// method return true if n is Happy numberbool isHappynumber(int n){ int slow, fast; // initialize slow and fast by n slow = fast = n; do { // move slow number by one iteration slow = numSquareSum(slow); // move fast number by two iteration fast = numSquareSum(numSquareSum(fast)); } while (slow != fast); // if both number meet at 1, then return true return (slow == 1);}// Driver code to test above methodsint main(){ int n = 13; if (isHappynumber(n)) cout << n << " is a Happy number\n"; else cout << n << " is not a Happy number\n";}// This code is contributed by divyeshrabadiya07 |
C
// C program to check a number is a Happy number or not#include <stdbool.h>#include <stdio.h>// Utility method to return sum of square of digit of nint numSquareSum(int n){ int squareSum = 0; while (n) { squareSum += (n % 10) * (n % 10); n /= 10; } return squareSum;}// method return true if n is Happy numberbool isHappynumber(int n){ int slow, fast; // initialize slow and fast by n slow = fast = n; do { // move slow number by one iteration slow = numSquareSum(slow); // move fast number by two iteration fast = numSquareSum(numSquareSum(fast)); } while (slow != fast); // if both number meet at 1, then return true return (slow == 1);}// Driver code to test above methodsint main(){ int n = 13; if (isHappynumber(n)) printf("%d is a Happy number\n", n); else printf("%d is not a Happy number\n", n);}// This code is contributed by Sania Kumari Gupta// (kriSania804) |
Java
// Java program to check a number is a Happy// number or notclass GFG { // Utility method to return sum of square of// digit of nstatic int numSquareSum(int n){ int squareSum = 0; while (n!= 0) { squareSum += (n % 10) * (n % 10); n /= 10; } return squareSum;} // method return true if n is Happy numberstatic boolean isHappynumber(int n){ int slow, fast; // initialize slow and fast by n slow = fast = n; do { // move slow number // by one iteration slow = numSquareSum(slow); // move fast number // by two iteration fast = numSquareSum(numSquareSum(fast)); } while (slow != fast); // if both number meet at 1, // then return true return (slow == 1);} // Driver code to test above methodspublic static void main(String[] args){ int n = 13; if (isHappynumber(n)) System.out.println(n + " is a Happy number"); else System.out.println(n + " is not a Happy number");}} |
Python3
# Python3 program to check a number# is a Happy number or not# Utility method to return # sum of square of digit of ndef numSquareSum(n): squareSum = 0; while(n): squareSum += (n % 10) * (n % 10); n = int(n / 10); return squareSum;# method return true if# n is Happy numberdef isHappynumber(n): # initialize slow # and fast by n slow = n; fast = n; while(True): # move slow number # by one iteration slow = numSquareSum(slow); # move fast number # by two iteration fast = numSquareSum(numSquareSum(fast)); if(slow != fast): continue; else: break; # if both number meet at 1, # then return true return (slow == 1);# Driver Coden = 13;if (isHappynumber(n)): print(n , "is a Happy number");else: print(n , "is not a Happy number");# This code is contributed by mits |
C#
// C# program to check a number// is a Happy number or notusing System;class GFG {// Utility method to return // sum of square of digit of nstatic int numSquareSum(int n){ int squareSum = 0; while (n!= 0) { squareSum += (n % 10) * (n % 10); n /= 10; } return squareSum;}// method return true if// n is Happy numberstatic bool isHappynumber(int n){ int slow, fast; // initialize slow and // fast by n slow = fast = n; do { // move slow number // by one iteration slow = numSquareSum(slow); // move fast number // by two iteration fast = numSquareSum(numSquareSum(fast)); } while (slow != fast); // if both number meet at 1, // then return true return (slow == 1);}// Driver codepublic static void Main(){ int n = 13; if (isHappynumber(n)) Console.WriteLine(n + " is a Happy number"); else Console.WriteLine(n + " is not a Happy number");}}// This code is contributed by anuj_67. |
PHP
<?php// PHP program to check a number// is a Happy number or not// Utility method to return // sum of square of digit of nfunction numSquareSum( $n){ $squareSum = 0; while ($n) { $squareSum += ($n % 10) * ($n % 10); $n /= 10; } return $squareSum;}// method return true if// n is Happy numberfunction isHappynumber( $n){ $slow; $fast; // initialize slow // and fast by n $slow = $n; $fast = $n; do { // move slow number // by one iteration $slow = numSquareSum($slow); // move fast number // by two iteration $fast = numSquareSum(numSquareSum($fast)); } while ($slow != $fast); // if both number meet at 1, // then return true return ($slow == 1);}// Driver Code$n = 13;if (isHappynumber($n)) echo $n , " is a Happy number\n";else echo n , " is not a Happy number\n";// This code is contributed by anuj_67.?> |
Javascript
<script>// Javascript program to check a number is a Happy// number or not// Utility method to return sum of square of// digit of nfunction numSquareSum(n){ var squareSum = 0; while (n!= 0) { squareSum += (n % 10) * (n % 10); n = parseInt(n/10); } return squareSum;} // method return true if n is Happy numberfunction isHappynumber(n){ var slow, fast; // initialize slow and fast by n slow = fast = n; do { // move slow number // by one iteration slow = numSquareSum(slow); // move fast number // by two iteration fast = numSquareSum(numSquareSum(fast)); } while (slow != fast); // if both number meet at 1, // then return true return (slow == 1);} // Driver code to test above methodsvar n = 13;if (isHappynumber(n)) document.write(n + " is a Happy number");else document.write(n + " is not a Happy number"); // This code contributed by Princi Singh </script> |
Output :
13 is a Happy Number
Complexity Analysis:
Time Complexity: O(n*log(n)).
Auxiliary Space: O(1).
Another approach for solving this problem using no extra space.
A number cannot be a happy number if, at any step, the sum of the square of digits obtained is a single-digit number except 1 or 7. This is because 1 and 7 are the only single-digit happy numbers. Using this information, we can develop an approach as shown in the code below –
C++
// C++ program to check if a number is a Happy number or// not.#include <bits/stdc++.h>using namespace std;// Method - returns true if the input is a happy number else// returns falsebool isHappynumber(int n){ if (n == 1 || n == 7) return true; int sum = n, x = n; // This loop executes till the sum of square of digits // obtained is not a single digit number while (sum > 9) { sum = 0; // This loop finds the sum of square of digits while (x > 0) { int d = x % 10; sum += d * d; x /= 10; } if (sum == 1) return true; x = sum; } if (sum == 7) return true; return false;}int main(){ int n = 13; if (isHappynumber(n)) cout << n << " is a Happy number"; else cout << n << " is not a Happy number"; return 0;}// This code is contributed by Sania Kumari Gupta |
C
// C program to check if a number is a Happy number or// not.#include <stdbool.h>#include <stdio.h>// Method - returns true if the input is a happy number else// returns falsebool isHappynumber(int n){ if (n == 1 || n == 7) return true; int sum = n, x = n; // This loop executes till the sum of square of digits // obtained is not a single digit number while (sum > 9) { sum = 0; // This loop finds the sum of square of digits while (x > 0) { int d = x % 10; sum += d * d; x /= 10; } if (sum == 1) return true; x = sum; } if (sum == 7) return true; return false;}int main(){ int n = 13; if (isHappynumber(n)) printf("%d is a Happy number", n); else printf("%d is not a Happy number", n); return 0;}// This code is contributed by Sania Kumari Gupta |
Java
// This code is contributed by Vansh Sodhi.// Java program to check if a number is a Happy number or not.class GFG { // method - returns true if the input is a happy // number else returns false static boolean isHappynumber(int n) { if (n == 1 || n == 7) return true; int sum = n, x = n; // this loop executes till the sum of square of // digits obtained is not a single digit number while(sum > 9) { sum = 0; // this loop finds the sum of square of digits while (x > 0) { int d = x%10; sum += d*d; x/=10; } if (sum == 1) return true; x = sum; } if(sum == 7) return true; return false; } // Driver code public static void main(String[] args) { int n = 13; if (isHappynumber(n)) System.out.println(n + " is a Happy number"); else System.out.println(n + " is not a Happy number"); }} |
Python3
# Python3 program to check if a number is a Happy number or not.# Method - returns true if the input is# a happy number else returns falsedef isHappynumber(n): if n == 1 or n == 7: return True Sum, x = n, n # This loop executes till the sum # of square of digits obtained is # not a single digit number while Sum > 9: Sum = 0 # This loop finds the sum of # square of digits while x > 0: d = x % 10 Sum += d * d x = int(x / 10) if Sum == 1: return True x = Sum if Sum == 7: return True return Falsen = 13 if isHappynumber(n): print(n, "is a Happy number")else: print(n, "is not a Happy number") # This code is contributed by mukesh07. |
C#
// C# program to check if a number // is a Happy number or not.using System;class GFG{// Method - returns true if the input is// a happy number else returns falsestatic bool isHappynumber(int n) { if (n == 1 || n == 7) return true; int sum = n, x = n; // This loop executes till the sum // of square of digits obtained is // not a single digit number while(sum > 9) { sum = 0; // This loop finds the sum of // square of digits while (x > 0) { int d = x % 10; sum += d * d; x /= 10; } if (sum == 1) return true; x = sum; } if (sum == 7) return true; return false;}// Driver codepublic static void Main(String[] args){ int n = 13; if (isHappynumber(n)) Console.WriteLine(n + " is a Happy number"); else Console.WriteLine(n + " is not a Happy number");}}// This code is contributed by 29AjayKumar |
Javascript
<script>// This code is contributed by Vansh Sodhi.// javascript program to check if a number is a Happy number or not. // method - returns true if the input is a happy // number else returns false function isHappynumber(n) { if (n == 1 || n == 7) return true; var sum = n, x = n; // this loop executes till the sum of square of // digits obtained is not a single digit number while(sum > 9) { sum = 0; // this loop finds the sum of square of digits while (x > 0) { var d = x % 10; sum += d * d; x /= 10; } if (sum == 1) return true; x = sum; } if(sum == 7) return true; return false;}// Driver code var n = 13; if (isHappynumber(n)) document.write(n + " is a Happy number"); else document.write(n + " is not a Happy number"); // This code is contributed by 29AjayKumar </script> |
Output
13 is a Happy number
Complexity Analysis:
Time Complexity: O(n*log(n)).
Auxiliary Space: O(1).
This article is contributed by Utkarsh Trivedi. 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!
