algoadvance

Leetcode 263. Ugly Number

Problem Statement

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 that 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.

Example:

Input: n = 19
Output: true
Explanation:
1² + 9² = 82
8² + 2² = 68
6² + 8² = 100
1² + 0² + 0² = 1

Clarifying Questions

1. Does n have any specific constraints (e.g. maximum value)?
   • Assume n is a positive integer.
2. Can the input number be 1?
   • Yes, and in this case, the output should be true.

Strategy

To determine if a number is a happy number:

1. Start with the given number.
2. Replace the number by the sum of the squares of its digits.
3. Use a set to track all previously seen sums to detect if there is a cycle.
4. If the number equals 1 at any point, return true.
5. If a previously seen sum appears again, return false.

This way, we can detect cycles which indicate that the number will not reach 1.

Code

#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 sum = 0;
        while (n > 0) {
            int digit = n % 10;
            n = n / 10;
            sum += digit * digit;
        }
        return sum;
    }
};

Time Complexity

• The time complexity is difficult to define exactly due to the nature of the problem. However, it is generally efficient because we are using a set to detect cycles, and operations on the set are O(1) on average. In practice, the number of iterations is relatively small.
• The space complexity is O(k), where k is the number of unique numbers we see before detecting a cycle or reaching 1. In the worst-case scenario, it can be logarithmic in the number of digits of n.

This approach ensures that we can efficiently detect happy numbers and avoid infinite loops caused by cycles.

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?