algoadvance

Leetcode 202. Happy Number

Problem Statement

Write an algorithm to determine if a number n is a happy number.

A happy number is a number defined by the following process:

• Starting with any positive integer, replace the number by the sum of the squares of its digits.
• Repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1.
• Those numbers for which this process ends in 1 are happy numbers.

Return true if n is a happy number and false if not.

Clarifying Questions

1. Range of Input: What is the range of input values (e.g., positive integers only)?
   • Assumption: The input will be a positive integer.
2. Edge Cases: Do we need to handle extremely large numbers?
   • For typical usage, standard constraints on integers in C++ should suffice.

Strategy

1. Step-by-Step Process:
   • Calculate the sum of squares of the digits.
   • Use a set to track the numbers we have seen to detect cycles.
   • Repeat until we encounter 1 (happy number) or detect a cycle (unhappy number).
2. Functions Needed:
   • A helper function to compute the sum of squares of digits.
   • A main function to implement the cycle detection using a set.

Code

#include <iostream>
#include <unordered_set>

class Solution {
public:
    bool isHappy(int n) {
        std::unordered_set<int> seen;
        
        while (n != 1 && seen.find(n) == seen.end()) {
            seen.insert(n);
            n = getNext(n);
        }
        
        return n == 1;
    }
    
private:
    int getNext(int n) {
        int totalSum = 0;
        while (n > 0) {
            int digit = n % 10;
            n = n / 10;
            totalSum += digit * digit;
        }
        return totalSum;
    }
};

int main() {
    Solution solution;
    int n = 19;  // Example input
    std::cout << (solution.isHappy(n) ? "True" : "False") << std::endl;
    return 0;
}

Explanation

• Helper Function getNext(int n):
  • Calculates the sum of the squares of the digits of n.
  • Splits n digit by digit and computes their squares to accumulate the total sum.
• Main Function isHappy(int n)
  • Uses an unordered set seen to track visited numbers.
  • Continuously calculates the next number using the getNext function.
  • If a number repeats (indicating a cycle), the process stops and returns false.
  • If the number becomes 1, the function returns true.

Time Complexity

• Each transformation step (calculation of the sum of the squares of the digits) operates in O(log n) time, where n is the current number.
• In the worst-case scenario, the transformation involves multiple steps before concluding (either by being happy or detecting a cycle).
• Hence, the overall complexity is hard to bound strictly but can be considered roughly O(k * log n), where k is the number of iterations before a cycle is detected or the number reaches 1. Typically, this converges quickly for most integers.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?