I don't think this is efficient. How can i improve?

Question

def happy(num):
numbr = num
sqr_sum = 0
while num != 1:
for i in str(num):
sqr_sum += int(i)**2
num = sqr_sum
sqr_sum = 0
if len(str(num)) == 1:
break
if num == 1:
print(f'\n{numbr} is Happy\n'.upper())
else:
print(f'{numbr} is not Happy')
low = int(input())
up = int(input())
for i in range(low, up+1):
happy(i)
Challenge:
https://www.sololearn.com/learn/4539/?ref=app
Solution:
https://code.sololearn.com/c0go493YHk6j/?ref=app

Answer 1

You can make it more efficient by memoization.
It means that you store and reuse calculations that you have already performed.
For example, as soon as you have proven that 10 is happy and 11 is unhappy, any further calculation with larger numbers can be derived from that intermediate result.
Such as with 13, 1*1 + 3*3 = 10 so you don't need to do the calculations for single digit again, it is proven that 13 is also happy.

Answer 2

Also, especially when you get into higher number ranges, you can notice that the order of digits does not matter.
12 and 21 are both unhappy.
13 and 31 are both happy.
With 2 digits you have only 2 combinations, but with 3 digits you have already 6 different ordering of digits, with 4 digits it's 24 orderings that give the same result.
So to use this efficiently for larger numbers, you need to memoize a set of digits.
In Python, a set cannot be used as a dictionary key, because it is not hashable, so you need to use a frozenset.
For example
{frozenset(1,3): True}
can mean that any number which has 1 and 3 as digits, is a happy number.
However there is one problem with this: if digits are repeated, this won't work.. Because a set eliminates duplicates. So frozenset is probably a bad option after all. You might still use a string or tuple as key, where the digits are already sorted, to reduce the number of keys.
{(2, 4, 4, 7): False}
Which gets you the same result for 7424, 4472 or 2744 too

Answer 3

Giorgos D I like the idea of the 10-tuple, I think for big numbers this can make a huge performance difference... Makes me wonder how high Python can go before it runs out of memory, or time out on SL 😅

Answer 4

Tibor Santa Sets aren't a good idea since we might have repeated numbers but i respect your awesome idea, since there are multiple combination of same group of digits in higher numbers we could also split the number by it zeros

Answer 5

Tibor Santa thank you so much

Answer 6

Giorgos D yeah its better to convert and save for memory efficiency but reduces performance greatly so is hardest and oldest programming question again memory or performance.

Answer 7

Some experiments with performance... It turns out the simplest solution is the fastest, using lru_cache has significant advantage.
@lru_cache
def h(n):
"""AutoCache"""
s = sum(d*d for d in map(int, str(n)))
return s == 1 if s < 10 else h(s)
Update: up to 500000, the fastest algotithm I found is storing the sorted digits in string, for the cache keys.
https://code.sololearn.com/cMez6b6oeLSm/?ref=app

Answer 8

You can use recursion to do it(hard part ) , like this :
https://code.sololearn.com/cDL9821WuZwf/?ref=app

Answer 9

You can also make your code more expressive and concise by using:
- recursion
- higher order function like map
- decorator functools.lru_cache for memoization.
As an example, the sum of squares of digits for any positive integer can be expressed like this:
sum(map(lambda n: int(n)**2, str(number)))

Answer 10

Tibor Santa To avoid the O(d*logd) complexity of sorting the digits, you can store the numbers as a tuple (immutable array) in this form of a size 10 array of counts:
digits: 11244477
tuple: (0,2,1,0,3,0,0,2,0,0)
0 1 2 3 4 5 6 7 8 9
You dont need any sorting for this, only a single pass of the digits O(d)

Answer 11

Giorgos D you should consider memory complexity
and what algorithm do you suggest for comparing two numbers

Answer 12

Abs Sh Even so, when the number gets bigger than 10^10 (ten digits long) this method stores just 10 ints, the sortes digits methods stores them all

Answer 13

Giorgos D You are not storing 10 int-4 since its python though

Answer 14

Abs Sh If both methods store as int32 then my method would use a constant 10*32 bits, storing the sorted digits would use num_digits*32 bits

Answer 15

Abs Sh But i think now what would be even more memory efficient would be to store the number itself after sorting the digits in descending order so 0 ends up last, only 32bits memory per number. But sorting gets it back to O(d*logd) time complexity, theres definitely a trade-off there

Answer 16

This thread is too interesting to leave alone :)
I think if memory is an issue to store a large number of keys in cache, maybe we can use a data type like bytearray(10) with memoryview
I have no idea though if that can work as dict key.
https://docs.python.org/3/library/stdtypes.html#bytearray
https://docs.python.org/3/library/stdtypes.html#memoryview
Another potential could be to use Counter object as key, although that one is surely not hashable, but maybe it can be customized by implementing a hash method. Raymond Hettinger surely knows what he's talking about.
https://stackoverflow.com/questions/1151658/python-hashable-dicts
https://code.sololearn.com/c7Oc7u9ulHhD/?ref=app

Answer 17

Harsha S
#Easy Part
num=13
def is_happy(n):
suum=sum([int(i)**2 for i in str(n)])
if suum==1:
return True
elif suum==4:
return False
else:
return is_happy(suum)
print(is_happy(num))
# Medium Part
#range
print([i for i in range(1,100) if is_happy(i)])

Answer 18

Tibor Santa
Ratnapal Shende
I tried the hard part
it's missing something
can you help?
#Hard:
num = '23'
def hapy(num):
sqr = 0
sqr_sum = []
for i in num:
sqr += int(i)**2
sqr_sum.append(sqr)
num = str(sqr)
sqr = 0
if sqr == 1 or 4:
sqr_sum.append(1)
else:
sqr_sum.append(hapy(num))
return [print(j) for j in sqr_sum]
hapy(num)

Answer 19

Harsha S I think for the hard part you would need to display how the result is reached. For example
Input: 23
Output:
2^2 + 3^2 = 13
1^2 + 3^2 = 10
1^2 + 0^2 = 1
23 is a happy number
You may have to add more than 2 digits, so you need a flexible solution. The join() method is very useful to combine any number of arguments into a single string.

Answer 20

Sω(ᗒ✧ᕙ☞Aᕗ✧ᗕ)ti
Jan Markus
Chethan TV
Tibor Santa
▬▬▬
Imadez
Ipang
Kesiya Jubil
Abhinav Kashyap
★ Don’t Know ★