Beautiful numbers in a range

Question

I've been asked this question somewhere .. you are given 2 integers l and r ..your task is to determine sum of all beautiful numbers in the range land r.

A number is a beautiful number if it satisfies the following conditions

• If a number becomes one at some point by replacing it repeatedly with the sum of squares of its digits. NOTE: If the number never becomes one then the provided number is not a beautiful number

For example, 32 is a happy number as the process yields 1 as follows

3^2 + 2^2 = 13
1^2 + 3^2 = 10
1^2 + 0^2 = 1

for range (31,32)...the answer is 31+32 = 63 ..as both are beautiful numbers.

I tried to do a recursive approach like this:

recursivefunction(int num){
        if(num == 1) return true;  
        //Calculates the sum of squares of digits  
        while(num > 0){  
            rem = num%10;  
            sum = sum + (rem*rem);  
            num = num/10;  
      
    }  
recursivefunction(sum);
}

Calling this function recursively for a range and stored the value in a sum if its 1, then add it into a sum variable.

And in question there was no breaking case. Like what I have to do when I don't find 1. So I put a counter like if it goes into recursion 10 times and still not 1 then return false.

But the thing is this function is giving time out in some if the test cases.

Answer 1

Then you can speed up the search by memoizing the non beautiful values. Here an example as pseudo-code (python)

theNonBeautiful = set() 

def isBeautiful(num, mySet = None):
    if mySet is None: 
        mySet = set()
    if(num == 1):
        return True
    if num in theNonBeautiful:
        return False
    sum_ = 0
    if num in mySet:
        return False
    mySet.add(num)
    while(num > 0):
        rem = num % 10;  
        sum_ = sum_ + (rem*rem);  
        num = (num - rem)/10;  
    value = isBeautiful(sum_, mySet);
    if(value == False): 
        theNonBeautiful.add(sum)
    return value

competitive programming problems provide you with the min, max size of the numbers in the range. You should try to do a big O analysis in order to understand if this algorithm is fast enough for your needs