CODEWITHSUNDEEP
pythonalgorithm
Ns68
Ns68

Reputation: 77

Happy number algorithm in Python

I'm solving Happy number algorithm problem

https://leetcode.com/problems/happy-number/

here is my code.

class Solution:
def isHappy(self, n):
    nums = str(n)
    while len(nums)!=1:
        result = 0
        for num in nums:
            result += int(num) * int(num)
        nums = str(result)
    if (nums == '1'): print("True")
    else: print("False")

if the total number of 1 is seven in input, it has an error. like ["1111111, 10111111", "11101111", "11011111"]

these numbers have to be True but results are False.

I know it needs to repeat one more while loop but every time I try to fix my code, I got more errors...

I don't have no clue how to fix this code. could you give me a hint?

Upvotes: 1

Views: 1213

Answers (5)

Sevelantis
Sevelantis

Reputation: 1

Simple unoptimized approach using cycle detection on earlier elements repetition. Store them in tabu.

def isHappy(n):
    tabu = []

    # initial calculations
    nums = list(map(int, str(n))) # 123 -> [1,2,3]
    sum = 0
    for x in nums:
        sum += x ** 2

    while True:
        # check return conditions
        if sum in tabu:
            return False
        elif sum == 1:
            return True

        nums = list(map(int, str(sum)))  # 123 -> [1,2,3]
        if sum not in nums:
            tabu.append(sum)
        sum = 0
        for x in nums:
            sum += x ** 2


assert isHappy(19) is True
assert isHappy(20) is False
assert isHappy(16) is False
assert isHappy(79) is True
assert isHappy(947) is False
assert isHappy(123) is False
assert isHappy(1233) is True
assert isHappy(16679) is True
assert isHappy(111319) is True

Upvotes: 0

Gamopo
Gamopo

Reputation: 1598

You'll need to use a list to save the numbers you've already been through, if you happen to fall into one of them again, you'll know you are in a cycle.

To stop the problem you're having, you should exit the while when one of the following conditions happen:

1-The result is exactly 1.

2-You find your result in the list of already checked.

Given this, here's how to fix your code, but I recommend you to try before checking the solution:

def isHappy(self, n):
    checked = []
    nums = str(n)
    while nums != '1' and not (nums in checked):
        checked.append(nums)
        result = 0
        for num in nums:
            result += int(num) * int(num)
        nums = str(result)
    if (nums == '1'): print("True")
    else: print("False")

Upvotes: 2

Access Denied
Access Denied

Reputation: 9461

The problem is that you terminate loop before it is '1'. You need to check nums != '1' in loop condition.

class Solution:
    def is_happy(self, n):
        checked_values = set()
        nums = str(n)
        while nums!='1':
            result = 0
            for num in nums:
                result += int(num) * int(num)
            nums = str(result)
            if nums in checked_values:
                print("False")
                return
            else:
                checked_values.add(nums)
        print("True")

Upvotes: 0

Patrick Artner
Patrick Artner

Reputation: 51623

The statements tells you that there are infinite loops - you need to remember which numbers you already checked to avoid cycles:

Input 2:

2 => 4 => 16 => 37 => 58 => 89 => 145 => 42 => 20 ===> 2 ===>  Cycle

Recursive approach:

class Solution:
    # remember all things we already saw - avoid endless loops
    seen = set()

    def isHappy(self, n: int) -> bool:
        if n in Solution.seen:
            # clear the cache for next try
            Solution.seen.clear()
            return False
        Solution.seen.add(n)

        s = sum(l*l for l in map(int,str(n)))

        if s == 1:
            # clear the cache for next try
            Solution.seen.clear()
            return True

        return self.isHappy(s)

s = Solution()

Test:

for i in range(30):
    if s.isHappy(i):
        print(f"Happy {i}")

Output:

Happy 1
Happy 7
Happy 10
Happy 13
Happy 19
Happy 23
Happy 28

Upvotes: 0

Alexander Lekontsev
Alexander Lekontsev

Reputation: 1012

Try something like this. If i got it right, the main condition to stop the loop is to get the same sum of numbers. You can store them in list(tuple) to check that.

class Solution:
    def isHappy(self, n: int) -> bool:
        nums = str(n)
        checked = []
        current_sum = 0
        while current_sum != 1:
            current_sum = sum(int(item)**2 for item in nums)
            if current_sum not in checked:
                checked.append(current_sum)
            else:
                return False
            nums = str(current_sum)
        return True

Upvotes: 1

Related Questions