Happy Numbers
A Happy Number n is defined by the following process. Starting with n, replace it with the sum of the squares of its digits, and repeat the process until n equals 1, or it loops endlessly in a cycle that does not include 1. Those numbers for which this process ends in 1 are Happy Numbers, while those that do not end in 1 are unhappy numbers.
First few happy numbers are 1, 7, 10, 13, 19, 23, 28, 31, 32, 44, 49, 68, 70, 79, 82, 86, 91, 94, 97, 100
Examples:
Input: 23
Output: Yes
Explanation :
First Iteration: 22 + 32 = 4 + 9 = 13
Second Iteration: 12 + 32 = 1 + 9 = 10
Third Iteration: 12 + 02 = 1 + 0 = 1. Since we reached 1, 23 is Happy.
The idea is simple, we repeated do sum of squares of digits. While doing so, we keep track of visited numbers using a hash. If we reach 1, we return true. Else if we reach a visited number, we return false.
Below is the implementation of the above approach:
// CPP program to check if a number
// is happy number
#include <bits/stdc++.h>
using namespace std;
// Returns sum of squares of digits
// of a number n. For example for n = 12
// it returns 1 + 4 = 5
int sumDigitSquare(int n)
{
int sq = 0;
while (n) {
int digit = n % 10;
sq += digit * digit;
n = n / 10;
}
return sq;
}
// Returns true if n is Happy number
// else returns false.
bool isHappy(int n)
{
// A set to store numbers during
// repeated square sum process
set<int> s;
s.insert(n);
// Keep replacing n with sum of
// squares of digits until we either
// reach 1 or we endup in a cycle
while (1) {
// Number is Happy if we reach 1
if (n == 1)
return true;
// Replace n with sum of squares
// of digits
n = sumDigitSquare(n);
// If n is already visited, a cycle
// is formed, means not Happy
if (s.find(n) != s.end())
return false;
// Mark n as visited
s.insert(n);
}
return false;
}
// Driver code
int main()
{
int n = 23;
if (isHappy(n))
cout << "Yes" << endl;
else
cout << "No" << endl;
return 0;
}
// Java program to check if a number
// is happy number
import java.util.*;
class GFG
{
// Returns sum of squares of digits
// of a number n. For example for n = 12
// it returns 1 + 4 = 5
static int sumDigitSquare(int n)
{
int sq = 0;
while (n > 0)
{
int digit = n % 10;
sq += digit * digit;
n = n / 10;
}
return sq;
}
// Returns true if n is Happy number
// else returns false.
static boolean isHappy(int n)
{
// A set to store numbers during
// repeated square sum process
HashSet<Integer> s = new HashSet<Integer>();
s.add(n);
// Keep replacing n with sum of
// squares of digits until we either
// reach 1 or we endup in a cycle
while (true)
{
// Number is Happy if we reach 1
if (n == 1)
return true;
// Replace n with sum of squares
// of digits
n = sumDigitSquare(n);
// If n is already visited, a cycle
// is formed, means not Happy
if ((s.contains(n) && n != (int)s.toArray()[ s.size()-1 ] ))
return false;
// Mark n as visited
s.add(n);
}
}
// Driver code
public static void main(String[] args)
{
int n = 23;
if (isHappy(n))
System.out.println("Yes");
else
System.out.println("No");
}
}
/* This code contributed by PrinciRaj1992 */
# python program to check if a number
# is happy number
# Returns sum of squares of digits
# of a number n. For example for n = 12
# it returns 1 + 4 = 5
def sumDigitSquare( n):
sq = 0;
while (n!=0):
digit = n % 10
sq += digit * digit
n = n // 10
return sq;
# Returns true if n is Happy number
# else returns false.
def isHappy(n):
# A set to store numbers during
# repeated square sum process
s=set()
s.add(n)
# Keep replacing n with sum of
# squares of digits until we either
# reach 1 or we endup in a cycle
while (True):
# Number is Happy if we reach 1
if (n == 1):
return True;
# Replace n with sum of squares
# of digits
n = sumDigitSquare(n)
# If n is already visited, a cycle
# is formed, means not Happy
if n in s:
return False
# Mark n as visited
s.add(n)
return false;
# Driver code
n = 23
if (isHappy(n)):
print("Yes")
else:
print("No")
// C# program to check if a number
// is happy number
using System;
using System.Collections.Generic;
class GFG
{
// Returns sum of squares of digits
// of a number n. For example for n = 12
// it returns 1 + 4 = 5
static int sumDigitSquare(int n)
{
int sq = 0;
while (n > 0)
{
int digit = n % 10;
sq += digit * digit;
n = n / 10;
}
return sq;
}
// Returns true if n is Happy number
// else returns false.
static bool isHappy(int n)
{
// A set to store numbers during
// repeated square sum process
HashSet<int> s = new HashSet<int>();
s.Add(n);
// Keep replacing n with sum of
// squares of digits until we either
// reach 1 or we endup in a cycle
while (true)
{
// Number is Happy if we reach 1
if (n == 1)
return true;
// Replace n with sum of squares
// of digits
n = sumDigitSquare(n);
// If n is already visited, a cycle
// is formed, means not Happy
if (s.Contains(n))
return false;
// Mark n as visited
s.Add(n);
}
}
// Driver code
public static void Main()
{
int n = 23;
if (isHappy(n))
Console.WriteLine("Yes");
else
Console.WriteLine("No");
}
}
// This code contributed by Rajput-Ji
// JavaScript program to check if a number
// is happy number
// Returns sum of squares of digits
// of a number n. For example for n = 12
// it returns 1 + 4 = 5
function sumDigitSquare(n)
{
let sq = 0;
while (n > 0)
{
var digit = n % 10
sq += digit * digit;
n = Math.floor(n / 10);
}
return sq;
}
// Returns true if n is Happy number
// else returns false.
function isHappy(n)
{
// A set to store numbers during
// repeated square sum process
let s = [];
s.push(n);
// Keep replacing n with sum of
// squares of digits until we either
// reach 1 or we endup in a cycle
while (true)
{
// Number is Happy if we reach 1
if (n == 1)
return true;
// Replace n with sum of squares
// of digits
n = sumDigitSquare(n)
// If n is already visited, a cycle
// is formed, means not Happy
if (s.includes(n))
return false
// Mark n as visited
s.push(n)
}
return false;
}
/// Driver code
let n = 23
if (isHappy(n))
console.log("Yes")
else
console.log("No")
// This code is contributed by phasing17
Output
Yes
Output:
Yes
Time complexity: O(log n) for a given number n
Auxiliary Space: O(n)
One important observation is, the cycle always contains 4. So we don’t need to keep track of all numbers. We can simply check for 4.
// A space optimized CPP program to check if a number is
// happy number
#include <bits/stdc++.h>
using namespace std;
// Returns sum of squares of digits of a number n.
// For example for n = 12 it returns 1 + 4 = 5
int sumDigitSquare(int n)
{
int sq = 0;
while (n) {
int digit = n % 10;
sq += digit * digit;
n = n / 10;
}
return sq;
}
// Returns true if n is Happy number else returns false.
bool isHappy(int n)
{
// Keep replacing n with sum of squares of digits until
// we either reach 1 or we end up in a cycle
while (1) {
// Number is Happy if we reach 1
if (n == 1)
return true;
// Replace n with sum of squares of digits
n = sumDigitSquare(n);
// Number is not Happy if we reach 4
if (n == 4)
return false;
}
return false;
}
// Driver code
int main()
{
int n = 23;
if (isHappy(n))
cout << "Yes" << endl;
else
cout << "No" << endl;
return 0;
}
// This code is contributed by Sania Kumari Gupta (kriSania804)
// A space optimized C program to check if a number is happy
// number
#include <stdbool.h>
#include <stdio.h>
// Returns sum of squares of digits of a number n.
// For example for n = 12 it returns 1 + 4 = 5
int sumDigitSquare(int n)
{
int sq = 0;
while (n) {
int digit = n % 10;
sq += digit * digit;
n = n / 10;
}
return sq;
}
// Returns true if n is Happy number else returns false.
bool isHappy(int n)
{
// Keep replacing n with sum of squares of digits until
// we either reach 1 or we end up in a cycle
while (1) {
// Number is Happy if we reach 1
if (n == 1)
return true;
// Replace n with sum of squares of digits
n = sumDigitSquare(n);
// Number is not Happy if we reach 4
if (n == 4)
return false;
}
return false;
}
// Driver code
int main()
{
int n = 23;
if (isHappy(n))
printf("Yes\n");
else
printf("No\n");
return 0;
}
// This code is contributed by Sania Kumari Gupta (kriSania804)
// A space optimized Java
// program to check if a
// number is happy number
import java.io.*;
class GFG {
// Returns sum of squares of
// digits of a number n. For
// example for n = 12 it
// returns 1 + 4 = 5
static int sumDigitSquare(int n)
{
int sq = 0;
while (n != 0)
{
int digit = n % 10;
sq += digit * digit;
n = n / 10;
}
return sq;
}
// Returns true if n is Happy
// number else returns false.
static boolean isHappy(int n)
{
// Keep replacing n with
// sum of squares of digits
// until we either reach 1
// or we end up in a cycle
while (true)
{
// Number is Happy if
// we reach 1
if (n == 1)
return true;
// Replace n with sum
// of squares of digits
n = sumDigitSquare(n);
// Number is not Happy
// if we reach 4
if (n == 4)
return false;
}
}
// Driver code
public static void main(String args[])
{
int n = 23;
if (isHappy(n))
System.out.println("Yes");
else
System.out.println("No" );
}
}
/*This code is contributed by Nikita tiwari.*/
# A space optimized Python3 program to
# check if a number is happy number
# Returns sum of squares of
# digits of a number n. For
# example for n = 12 it
# returns 1 + 4 = 5
def sumDigitSquare(n) :
sq = 0
while (n) :
digit = n % 10
sq = sq + digit * digit
n = n // 10
return sq
# Returns true if n
# is Happy number else
# returns false.
def isHappy(n) :
# Keep replacing n with
# sum of squares of digits
# until we either reach 1
# or we end up in a cycle
while (1) :
# Number is Happy if
# we reach 1
if (n == 1) :
return True
# Replace n with sum of
# squares of digits
n = sumDigitSquare(n)
# Number is not Happy
# if we reach 4
if (n == 4) :
return False
return False
# Driver code
n = 23
if (isHappy(n)) :
print("Yes")
else :
print("No")
# This code is contributed
# by Nikita tiwari.
// A space optimized C#
// program to check if a
// number is happy number
using System;
class GFG
{
// Returns sum of squares of
// digits of a number n. For
// example for n = 12 it
// returns 1 + 4 = 5
static int sumDigitSquare(int n)
{
int sq = 0;
while (n != 0)
{
int digit = n % 10;
sq += digit * digit;
n = n / 10;
}
return sq;
}
// Returns true if n is Happy
// number else returns false.
static bool isHappy(int n)
{
// Keep replacing n with
// sum of squares of digits
// until we either reach 1
// or we end up in a cycle
while (true)
{
// Number is Happy if
// we reach 1
if (n == 1)
return true;
// Replace n with sum
// of squares of digits
n = sumDigitSquare(n);
// Number is not Happy
// if we reach 4
if (n == 4)
return false;
}
}
// Driver code
static public void Main ()
{
int n = 23;
if (isHappy(n))
Console.WriteLine("Yes");
else
Console.WriteLine("No" );
}
}
// This code is contributed by ajit
<script>
// A space optimized Javascript
// program to check if a
// number is happy number
// Returns sum of squares of
// digits of a number n. For
// example for n = 12 it
// returns 1 + 4 = 5
function sumDigitSquare(n)
{
let sq = 0;
while (n != 0)
{
let digit = n % 10;
sq += digit * digit;
n = parseInt(n / 10, 10);
}
return sq;
}
// Returns true if n is Happy
// number else returns false.
function isHappy(n)
{
// Keep replacing n with
// sum of squares of digits
// until we either reach 1
// or we end up in a cycle
while (true)
{
// Number is Happy if
// we reach 1
if (n == 1)
return true;
// Replace n with sum
// of squares of digits
n = sumDigitSquare(n);
// Number is not Happy
// if we reach 4
if (n == 4)
return false;
}
}
let n = 23;
if (isHappy(n))
document.write("Yes");
else
document.write("No" );
</script>
<?php
// A space optimized PHP
// program to check if a
// number is happy number
// Returns sum of squares
// of digits of a number
// n. For example for n = 12
// it returns 1 + 4 = 5
function sumDigitSquare($n)
{
$sq = 0;
while ($n)
{
$digit = $n % 10;
$sq += $digit * $digit;
$n = $n / 10;
}
return $sq;
}
// Returns true if n
// is Happy number
// else returns false.
function isHappy($n)
{
// Keep replacing n with
// sum of squares of digits
// until we either reach 1
// or we end up in a cycle
while (1)
{
// Number is Happy
// if we reach 1
if ($n == 1)
return true;
// Replace n with sum
// of squares of digits
$n = sumDigitSquare($n);
// Number is not Happy
// if we reach 4
if ($n == 4)
return false;
}
return false;
}
// Driver code
$n = 23;
if (isHappy($n))
echo "Yes";
else
echo "No";
// This code is contributed by mits
?>
Output
Yes
Output:
Yes
Time complexity: O(log N) where N is no of digits of a given number n
Auxiliary Space : O(1)
Contact Us