Beautiful Number

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.

Both 31 and 32 can be shown to be Beautiful Numbers as shown below. 31 -> 3^2 + 1^2 = 10 10 -> 1^2 +0^2 = 1 32 -> 3^2 + 2^2 = 13 13 -> 1^2 + 3^2 = 10 10 -> 1^2 = 1 Hence the num = 31 + 32 = 63. It can be shown that no other numbers in the given interval are beautiful.

Brute Force - Using memoization

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 9²* 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

Set number as visited in hashmap

3. Return answer

Time Complexity

O( ( R - L ) ), Where ‘T’ is the number of test cases and ‘L’ and ‘R’ are the ends of the interval.

As we are iterating over all the elements from ‘L’ to ‘R’ once.

Hence the time complexity is O( ( R - L ) ).

Space Complexity

O( 1 ).

As we are using a constant number of extra variables and the number of elements in any loop is very small.

Hence the space complexity is O( 1 ).

Problem statement

Sample Input 1 :

Sample Output 1 :

Explanation Of Sample Input 1 :

Sample Input 2 :

Sample Output 2 :