[Solution]Problem 51:Happy Number[IBM]

Hope you're excited

To learn more about the newsletter, check our detailed About Page + FAQs

To help me understand you better, please fill out this anonymous, 2-min survey. If you liked this post, make sure you hit the heart icon in this email.

Recommend this publication to Substack over here

---

I’m sure you couldn’t wait for this,

One of my subs was asked this question in their IBM software engineering interview. I thought about this question for quite a while, trying and testing different variants.

This problem can be found as problem 202. Happy Number on Leetcode.

Problem

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

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.

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

Example 1:

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

Example 2:

Input: n = 2
Output: false

Constraints:

• 1 <= n <= 231 - 1

You can test your solution here

[FREE SUBS]To buy the solution for this problem, use any of the following links. The price is 3 USD. Once you send the payment, message me on IG, LinkedIn, Twitter, or by Email:

Venmo: https:/ount.venmo.com/u/FNU-Devansh

Paypal: paypal.me/ISeeThings

Or you can sign up for a Free Trial Below. Since the reception has been great, I got a special offer for y’all. You can get this newsletter free for 2 months, just by using the button below-

Step 1: Analyzing the Definitions

In such cases, I believe it is best to attack by trying to break down the definitions given in the problem. By clearly defining the problem and all the definitions, we can gain a lot of insight into the problem. And in many cases, it can help you come up with mathematical rules and formulations that will let you solve the problem much quicker than average. This might just be my Math Degree, and work in AI, but this approach is definitely a competitive advantage. There aren’t many software people that actively try to look for patterns or mathematical/algorithmic statements. Even when you can’t come up with complete functions to generate the output, you will gain some insights into how to solve/optimize this problem.

I like to go bottom-up when attacking definitions, going with the simplest first. Regular readers know how powerful going for low-hanging fruit is, especially in contexts like the interview where you’re expected to communicate your thoughts in a coherent manner. So let’s attack the smallest definition we can see- what does it mean for a number to loop endlessly?

This might seem obvious to y’all, but take a step back. How would you define an infinite loop? Some numbers might just take a very very very long time to converge to happiness, but they aren’t unhappy. Calling them unhappy would be wrong, and would probably hurt their feelings.

So let’s wrack our brains to see if we can come up with something. Think back to how you can tell if we are stuck in a loop. What definitions are used commonly?

Step 2: Cycling

Notice something about the problem. Given a number x, we can only go to one other y. For example, given 2, we can only generate 4. Thanks to the rules given, we can’t go to different numbers, given an input. Our solution is deterministic (just a fancy math term for those of you that really want to assert your dominance on the interviewers).

This means that if we have already seen a number during a run, we are stuck in a cycle. We already know where we will go from here, and that we will eventually come back to this point. We’re going to be running around in circles.

As a tangent, notice how this is an extremely simplified graph cycle detection problem. Pretty neat huh? Image Source

If you spotted this before this point, give yourself a pat on the back. Great insight. If you weren’t able to, don’t beat yourself up too much. It takes time and effort to get good at this. Now that you’re here, just show up and do the work. Your results are guaranteed. Now let’s get back to the problem.

Thus we can apply the standard cycle detection algorithms to go through things quickly. The best way to do this is to keep a set to keep track of the visited nodes. While this could be done using Floyd’s algorithm, this approach doesn’t seem to work to perform too well in practice. This is because, for large cycles, the convergence is relatively slow. Our solution uses up a little more memory, but will always stop at the first common node. Floyd’s Cycle Detection will not do so (but requires less memory).

Using fast and slow pointers is a pretty handy skill. Nothing wrong with walking through this. Source

Make sure you explore this tradeoff in your interviews. Both solutions will have the same Big O time complexity, but using a set will typically be faster. Ask your interviewer which they would prefer (this really shows both your knowledge and ability to consider alternatives). I’m going to share the solution using a set, but make sure you practice both. If any of you premium subs want the other solution, just reply to this email (or use the links below) and let me know. However, first I’d recommend building the alternative on your own for the most benefits.

Code

Once we know to detect the cycles, the code is relatively simple. Take a look below.

class Solution:
    def isHappy(self, n: int) -> bool:
        
        def squareDigits(old_n):
            new_n = 0
            while old_n > 0:
                digit = old_n % 10
                new_n += pow(digit, 2)
                old_n //= 10
            return new_n
            
        seen = set()
        while n!=1 and n not in seen:
            seen.add(n)
            n = squareDigits(n)
            
        return n==1

Time Complexity- O(n).

Space Complexity- O(n)

Loved the solution? Hate it? Want to talk to me about your crypto portfolio? Get my predictions on the UCL or MMA PPVs? Want an in-depth analysis of the best chocolate milk brands? Reach out to me by replying to this email, in the comments, or using the links below.

Stay Woke. I’ll see you living the dream.

Go kill all,

Devansh <3

Reach out to me on:

Instagram: https://www.instagram.com/iseethings404/

Message me on Twitter: https://twitter.com/Machine01776819

My LinkedIn: https://www.linkedin.com/in/devansh-devansh-516004168/

My content:

Read my articles: https://rb.gy/zn1aiu

My YouTube: https://rb.gy/88iwdd

Get a free stock on Robinhood. No risk to you, so not using the link is losing free money: https://join.robinhood.com/fnud75