Last Updated: 3 Jun, 2022
Beautiful Number
Moderate
Asked in companies
Ninja loves beautiful numbers and also has two integers, ‘L’ and ‘R’, denoting an interval [L, R].
Given the interval [L, R], Ninja wants you to find the number of Beautiful numbers in the interval.
A Beautiful Number is a number that:
Becomes 1 by repeatedly replacing the number with the sum of squares of its digits.
If the number does not become 1, then it’s not a Beautiful Number.
For example, given interval = [1, 3]
We see that 1 is a Beautiful Number but 2,3 are not. Hence the answer is 1.
Output the single integer, the sum of all Beautiful Numbers in the given range.
Example:
Input: ‘L’ = ‘1’ , 'R' = ‘3’
Output: 1
As ‘1’ is the only Beautiful Number.
3 is not Beautiful as,
3 -> 9
9 -> 81
81 -> 65
65 -> 61 … and so on
It can be shown that we cannot get 1.
Input Format :
The first line will contain the integer 'T', denoting the number of test cases.
For each test case, the first line contains two integers ‘L’ and ‘R’ denoting the ends of an interval.
Output format :
For each test case, print a single integer representing the sum of all Beautiful Numbers in the given interval [L, R].
Note :
You don't need to print anything. It has already been taken care of. Just implement the given function.
Constraints :
1 <= T <= 50
1 <= L <= R <= 10^5
Time Limit: 1 sec
Approaches
We will iterate over all natural numbers in the range [L, R], and for each number, we will simulate the process to determine if the ‘i’th number is a Beautiful Number.
However, this may result in an infinite loop as the numbers are repeated while operating. We can use a Hashmap to memorize the visited numbers.
Now we are using Hashmap for representing that if the number is not beautiful then after some operation a number ‘D’ may or may not be equal to the actual number provided.
So now to prove that the number ‘D’ will repeat itself let us assume that a number ‘K’ which has the number of digits >= ‘4’ let us denote the number of digits by ‘d’ for the current number. We know the maximum number that can be generated by the current number is 92 * d for d = 4 the number can at most be 81 * 4 = 324.
Now if there is no cycle to exist the number after some operation should go beyond ‘K’ as there are finite numbers between 2 to K. But for greater numbers like d = 4 (Where d is the number of digits) max value we can get is 324 which is less then ‘K’ and to get greater value the number of digits should increase as the result directly depends on the number of digits.
But to get get more digits we need bigger numbers but as the value is reduced with the first operation as shown above the number of digits will decrease as well, So we can not go beyond ‘K’. So there will be a cycle there and the number ‘D’ will repeat itself.
If we reach a value ‘x’ for the second time while checking for the same number, then there exists a loop, and the current number cannot be converted to ‘1’.
The steps are as follows :
- Iterate over elements from ‘L’ to ‘R’.
- Check if the given number is Beautiful by simulating the process.
- If the number becomes ‘1’
- Add the ‘i’th element to the answer.
- Else if the number is visited:
- Break out of the loop
- If the number becomes ‘1’
Set number as visited in hashmap
3. Return answer
The idea is to use an upper bound to determine if the number can be reduced to ‘1’. We can observe that the numbers part of a cycle will never reach ‘1’.
And those numbers that are not a part of a cycle will reach ‘1’ quickly.
Let us consider 99999 as the number, in one operation we replace it with (9^2)*5 = 405. The number decreases very quickly for very large numbers, hence we can safely assume that in less than log(number) operations (as at least one digit will reduce during the operation when no cycle is encountered), we can easily reach 1.
Let us assume a safe upper bound of 60.
We can use this fact to check whether the number is beautiful or not without using a hashmap.
The steps are as follows :
- Iterate over elements from ‘L’ to ‘R’.
- Check if the given number is Beautiful by simulating the process at most 60 times.
- If number becomes ‘1’
- Add the ‘i’th element to the answer.
- Return answer
Similar problems