Beautiful numbers in a range

user_1987900 0
Viewed 6197

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

example : 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 apporch 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 fount 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 .

data-structures algorithm
4 Answers

Are you checking if the function is not entering in a loop? You should consider memoizing (in a set) the visited values

You can start from something like this:

def isBeautiful(num, mySet = None):
    if mySet is None: 
        mySet = set()
    if(num == 1):
        return True
    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;  
    return isBeautiful(sum_, mySet);

but this can be furtherly optimized... for instance by memoizing the "non beautiful" values

user_5122250

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

user_5122250

Previous solution is great but for missing out on number '7' which is returned as beautiful while it is obviously not. I feel a check can be placed in code to explicitly mark-off single digits except '1' as non-beautiful. Hence my take on the solution as below:


non_beauty_set = set() #memoizing non beautiful numbers for subsequent checks

def is_beautiful(num:int, myset=None):
    sum_dig = 0 # initiliazing sum of digits
    if myset is None:
        myset = set() # initilaizing myset if no set is passed as argument
    if (num == 1):
        return True
    if ((num in non_beauty_set) or (num in myset) or (1<num<=9) or (num==0)):
        return False
    myset.add(num) # memoizing num for subsequent checks for sum of digits
    for x in str(num):
        sum_dig += int(x) * int(x)
    is_sum_beautiful = is_beautiful(sum_dig, myset) # recursive check for sum of square of digits
    if is_sum_beautiful == False:
        non_beauty_set.add(sum_dig)
    return is_sum_beautiful
user_167146070

Below is mine C++ code:

#include <iostream>

using namespace std;


bool check(int num){
    
    if(num==1 || num ==7)
        return true;
    else if(num%10==num)
        return false;
        
    
    int n=0;
    while(num){
        int k = num%10;
        n = n+ (k*k);
        num = num/10;
        
    }
        
    check(n);
}


int main()
{
    int num;
    cin>>num;
    if(check(num))
        cout<<"Yes"<<endl;
    else
        cout<<"No"<<endl;
    return 0;
}
user_81514430
Related