Join Regular Classroom : Visit ClassroomTech

HackWithInfy 2021 Sample Question-A (Beautiful Function) Solution

 

Problem Statement: Let’s define a Beautiful Function F(x) in such a way: Add 1 to the value of x, if the result of addition contains any trailing zeros then remove them all.

Example:
F(11) = 12
F(19) = 2 (20 –> 2)
F(99) = 1(100 –> 10 –> 1)

Let’s define a number to be reachable from x , if we can apply Beautiful Function some number of times (possibly zero) to x and get that number as result
Ex. 102 can be reachable from 1099 as F(F(1099)) = F(101) = 102
You are given a number N . Calculate how many numbers are reachable from N.

Input Format:
The first line contains an integer N. denoting the given number.

Constrains: 1 <= N <= 10^9

Sample InputSample outputExplanation
191,2,3,4,5,6,7,8,9 are reachable from 1.

Let’s Understand the problem first: In this problem, you will be given a number you have to find how many numbers can be reachable from the given no using the Beautiful function.

The beautiful function is also very simple you just have to add 1 with the given input number  and have to check whether it has any trailing zero or not if it has trailing zeros we have to remove those zeros to get the output number of the function.

Tricks to solve the problem: As reading the question you can guess that we have to use beautiful function multiple times so it can be easily solved using recursion function . But the question is when we have to stop the recursion or what will be the exit condition in case of the problem??

So the exit condition will be we have to make a list of all the visited numbers from the given input number and if any case we get a same number which has already been visited then numbers will be start repeating so in that case we have to stop the recursion and length of the list will be the final output of the program.

Solution: Here is our solution in python. We strongly recommend you to attempt the problem first before moving to our given solution for your betterment.

# HackWithInfy 2021 Sample Question-A (Beautiful Function) Solution
# www.codewindow.in

count=0
r=[]
def func1(c):
    global r
    global count
    if c in r:
        return
    else:
        r.append(c)
        c=c+1
        c=str(c)
        c=c.rstrip('0')
        c=int(c)
        count=count+1
        func1(c)
     
     
n=int(input())
count=0
func1(n)
print(count)

Let’s Understand the code line by line: First off all I needed a count variable for counting the output and a list r to store all the values possible to visit from the given input number. We can do it by two ways as passing the list and count variable in each recursive call or we can do it but making them global variable. We have made them global in our solution.

Now coming in the driving code first we have taken input and typecasting it into int. We have made count variable as 0 for initial setting. Then we are calling func1 which is the original beautiful function and passing the initial input value in the function.

Now let’s look into the beautiful function. We have taken the global list r and the count variable inside the function and we are checking if the number is already available in list or not? If the number is previously present in the list we perform break and end the recursive calling. If not present in the list we are adding the new value in the list and then performing the beautiful function operation.

We are adding 1 with the number and changing it to a string by using str() command . Lets understand it by using a example suppose our input is 99 in beautiful function we add 1 then it becomes 100. We typecast it in string then it becomes 100 in string format. Now we are applying rstrip(‘0’) methods in string to remove the right side ‘0’ characters . So the string “100” after removing right side ‘0’ characters will become “1” then we again typecast it into int to get the value. We increase the value of count by 1 and we call again the func1() by giving the newly generated value as input. And at last in the driving code we print the count to get the value of output which is number of values possible to visit from the given input number.

Proof of successful running the code: Here is the proof that our code was successfully accepted by online judge.


 


Recent Posts