Skip to main content

Next Happy Number (Geeks for Geeks)

This tutorial contains a complete walk-through of the Next Happy Number problem from the Geeks for Geeks website. It features the implementation of the solution code in three programming languages: Python, C++, and Java.

Problem Statement​

For a given non-negative integer N, find the next smallest Happy Number. A number is called Happy if it leads to 1 after a sequence of steps, where at each step the number is replaced by the sum of squares of its digits. If we start with a Happy Number and keep replacing it with the sum of squares of its digits, we eventually reach 1.

Examples​

Example 1:

input:
N = 8

Output:
10

Explanation: Next happy number after 8 is 10 since [1∗1+0∗0=1][ 1 * 1 + 0 * 0 = 1]

Example 2

Input:
N = 10

Output:
13

Explanation:

After 10, 13 is the smallest happy number because [1∗1+3∗3=10][1 * 1 + 3 * 3 = 10], so we replace 13 by 10 and [1∗1+0∗0=1][1 * 1 + 0 * 0 = 1].

Task​

You don't need to read input or print anything. Your task is to complete the function nextHappy() which takes an integer N as input parameters and returns an integer, the next Happy number after N.

Constraints​

  • (1≤N≤105)(1 \leq N \leq 10^5)

Solution Approach​

Intuition​

To solve the problem, we need to:

  1. Identify the next number greater than N.
  2. Check if it is a Happy Number.
  3. Repeat the process until we find the next Happy Number.

A number is identified as Happy if, by repeatedly replacing it with the sum of squares of its digits, we eventually reach 1.

Steps​

  1. Implement a helper function to determine if a number is Happy.
  2. Start checking numbers greater than N, using the helper function to identify the next Happy Number.

Detailed Explanation​

The numbers that, when you repeatedly sum the squares of their digits, eventually result in 1 are known as "happy numbers."

Here are examples of how to determine if numbers less than 10 are happy numbers:

  • Number 1:

    [12=1][1 ^ 2 = 1] Since we have already reached 1, the process stops here. 1 is a happy number.

  • Number 2:

    [22=4][2^2 = 4] [42=16][4^2 = 16] [12+62=37][1^2 + 6^2 = 37] [32+72=58][3^2 + 7^2 = 58] [52+82=89][5^2 + 8^2 = 89] [82+92=145][8^2 + 9^2 = 145] [12+42+52=42][1^2 + 4^2 + 5^2 = 42] [42+22=20][4^2 + 2^2 = 20] [22+02=4][2^2 + 0^2 = 4]

    Since we have reached 4 again, the process will continue in an infinite loop. 2 is not a happy number.

  • Number 3:

    Similar to the above steps, 3 will also enter a loop and is not a happy number.

  • Number 4:

    Similar to the above steps, 4 will also enter a loop and is not a happy number.

  • Number 5:

    Similar to the above steps, 5 will also enter a loop and is not a happy number.

  • Number 6:

    Similar to the above steps, 6 will also enter a loop and is not a happy number.

  • Number 7:

    [72=49][7^2 = 49] [42+92=97][4^2 + 9^2 = 97] [92+72=130][9^2 + 7^2 = 130] [12+32+02=10][1^2 + 3^2 + 0^2 = 10] [12+02=1][1^2 + 0^2 = 1]

    Since we have reached 1, the process stops here. 7 is a happy number.

  • Number 8:

    Similar to the above steps, 8 will also enter a loop and is not a happy number.

  • Number 9:

    Similar to the above steps, 9 will also enter a loop and is not a happy number.

Based on this analysis, the numbers less than 10 that result in 1 when you repeatedly sum the squares of their digits are: 1 and 7.

Implementation​

Code (C++):​

#include <iostream>

class Solution {
public:
bool solve(int n) {
if (n == 1 || n == 7) return true;
if (n == 2 || n == 4 || n == 8 || n == 3 || n == 9 || n == 5 || n == 6) return false;
int sq_sum = 0;
while (n) {
int x = n % 10;
sq_sum += (x * x);
n /= 10;
}
return solve(sq_sum);
}

int nextHappy(int n) {
while (true) {
n++;
if (solve(n)) return n;
}
}
};

int main() {
Solution sol;
int N = 8;
std::cout << "Next happy number after " << N << " is: " << sol.nextHappy(N) << std::endl;
return 0;
}

Code(Python)​

class Solution:
def solve(self, n: int) -> bool:
if n == 1 or n == 7:
return True
if n in {2, 4, 8, 3, 9, 5, 6}:
return False
sq_sum = 0
while n > 0:
x = n % 10
sq_sum += (x * x)
n //= 10
return self.solve(sq_sum)

def nextHappy(self, n: int) -> int:
while True:
n += 1
if self.solve(n):
return n

# Example usage
sol = Solution()
N = 8
print(f"Next happy number after {N} is: {sol.nextHappy(N)}")

Code (Java)​

public class Solution {
public boolean solve(int n) {
if (n == 1 || n == 7) return true;
if (n == 2 || n == 4 || n == 8 || n == 3 || n == 9 || n == 5 || n == 6) return false;
int sq_sum = 0;
while (n > 0) {
int x = n % 10;
sq_sum += (x * x);
n /= 10;
}
return solve(sq_sum);
}

public int nextHappy(int n) {
while (true) {
n++;
if (solve(n)) return n;
}
}

public static void main(String[] args) {
Solution sol = new Solution();
int N = 8;
System.out.println("Next happy number after " + N + " is: " + sol.nextHappy(N));
}
}

Complexity​

  • Time Complexity: O(klog10N)O(klog_{10}N) due to the operations on digits of the numbers.

Explanation :​

  • We will be able to determine whether a number is happy or not after recursively calling the solve function and adding the square of its digits for a maximum of 15-20 times (you can check for any random value less than 10^5). Let's denote this value as x.

  • The time taken to add the square of the digits is log10(n). Furthermore, as we are checking until we find the happy number, let's denote the number of iterations as c = (happy number>n) -n

  • Let's denote x*c=k; Therefore, TC: (klog10(n))

  • The value of k won't even reach 10^4 or 10^5. You can try this approach with any random value.

  • Space Complexity: O(1)O(1) since we only use a fixed amount of extra space for the set to store seen numbers.

Conclusion​

To find the next Happy Number after a given integer N, we can implement a solution that iteratively checks each number greater than N until a Happy Number is found. This solution efficiently identifies Happy Numbers using a helper function to compute the sum of squares of digits and a set to track previously seen numbers to avoid infinite loops.

References​