+ 7

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

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

19th Aug 2021, 7:09 PM
Harsha S
+ 10
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.
19th Aug 2021, 7:46 PM
Tibor Santa
+ 6
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
19th Aug 2021, 8:09 PM
Tibor Santa
+ 5
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 π
19th Aug 2021, 8:33 PM
Tibor Santa
+ 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
19th Aug 2021, 8:23 PM
Abs Sh
+ 3
Tibor Santa thank you so much
19th Aug 2021, 7:47 PM
Harsha S
+ 3
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.
19th Aug 2021, 8:49 PM
Abs Sh
+ 3
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
20th Aug 2021, 4:48 AM
Tibor Santa
+ 3
You can use recursion to do it(hard part ) , like this : https://code.sololearn.com/cDL9821WuZwf/?ref=app
21st Aug 2021, 5:50 AM
TCorn
+ 2
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)))
19th Aug 2021, 7:49 PM
Tibor Santa
+ 2
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)
19th Aug 2021, 8:27 PM
Giorgos
+ 2
Giorgos D you should consider memory complexity and what algorithm do you suggest for comparing two numbers
19th Aug 2021, 8:30 PM
Abs Sh
+ 2
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
19th Aug 2021, 8:34 PM
Giorgos
+ 2
Giorgos D You are not storing 10 int-4 since its python though
19th Aug 2021, 8:36 PM
Abs Sh
+ 2
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
19th Aug 2021, 8:38 PM
Giorgos
+ 2
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
19th Aug 2021, 8:43 PM
Giorgos
+ 2
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
19th Aug 2021, 8:55 PM
Tibor Santa
+ 2
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)])
20th Aug 2021, 5:47 AM
Ratnapal Shende
+ 2
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)
20th Aug 2021, 7:12 AM
Harsha S
+ 2
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.
20th Aug 2021, 8:49 AM
Tibor Santa
19th Aug 2021, 7:10 PM
Harsha S