Good Number

Moderate
0/80
profile
Contributed by
17 upvotes
Asked in companies
ApplePayPalAdobe

Problem statement

You are given an integer ‘N’, you need to find whether it’s a good number or not.

We start from the integer ‘N’ and keep replacing the current number with the sum of squares of its digits, we keep repeating this process until we will the number 1. A number that generates the 1 after finite repetition of the above process is called a good number.

Example : 
If ‘N’ = 7,

Then we start with the integer 7 and replace it with (7 * 7) = 49.
The new number is 49, we replace it with (4 * 4) + (9 * 9) = 97.
We replace this new number 97 with (9 * 9) + (7 * 7) = 130.
We replace this new number 130 with (1 * 1) + (3 * 3) + (0 * 0) = 10.
We replace this new number 10 with (1 * 1) + (0 * 0) = 1.

Therefore, the original number 7 is a good number.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains a single integer ‘T’ denoting the number of test cases, then each test case follows:

The first line of each test case contains a single integer ‘N’, denoting the input number.
Output Format : 
For each test case, print “true” if the number is a good number, else print “false”.

Output for each test case will be printed in a separate line.
Note : 
You are not required to print anything; it has already been taken care of. Just implement the function.
Constraints : 
1 ≤ ‘T’ ≤ 10      
1 ≤ N ≤ 10000    

Time limit: 1 sec
Sample Input 1 :
2
7
2
Sample Output 1 :
true
false
Explanation For Sample Input 1 :
For test case 1 :
We will print “true” because:
We start with the input integer 7 and replace it with (7 * 7) = 49.
The new number is 49, we replace it with (4 * 4) + (9 * 9) = 97.
We replace this new number 97 with (9 * 9) + (7 * 7) = 130.
We replace this new number 130 with (1 * 1) + (3 * 3) + (0 * 0) = 10.
We replace this new number 10 with (1 * 1) + (0 * 0) = 1.
Therefore, the original number 7 is a good number.

For test case 2 : 
We will print “false” because:
If we start replacing the number 2 with the sum of the square of its digits then we will not be able to reach the number 1 even after infinite steps.
Sample Input 2 :
2
1
1045
Sample Output 2 :
true
false
Hint

A loop always exists if the given number is not a good number.

Approaches (2)
Hashing

Intuitively one may figure out that for a number that is not good we will get a loop, that is we will start generating a number that was generated earlier, and thereafter we will get stuck in this infinite loop and won’t be able to reach 1.

 

But is this condition enough, the answer to that is YES!

 

One may argue that a condition might be possible where the given number is not good and will generate infinitely many numbers as a loop won’t exist, but this will never happen, let us discuss why: Let’s start with a claim that an upper bound must exist on the range of the number for a loop to exist (just to avoid infinitely many numbers being generated), let that upper bound number be ‘U’ for a while, and let the function d(U) denote the number of digits in the U, if all the numbers in U are equal to 9 then one may get the next number is equal to 81 * d(U), one may also easily conclude that 81 * d(U) < 100 * d(U). Therefore, the number of digits in this new number which is equal to d(81*d(U)) will be less than d(100*d(U)), we can simplify this to conclude that number of digits in the new number will be less than 2 + d(U), in the best case when all the digits of this new number are equal to 9 then the maximum possible value of this new number will be 9 * ( 2 + d(U) ) which is clearly less than the value of U, therefore, we can conclude that an upper bound U will always exist and a number which is not a good number will have a cycle.

 

We can now use a simple hash-set to keep the track of numbers we have already generated. And in future, if we regenerate this number then we can say that an infinite loop exists and return “false”. Else we will reach the number 1 and return “true” in that case.

 

The steps are as follows :

  1. Declare a hash set ‘hashSet’ to store all the numbers generated so far.
  2. Run a while loop till the current number ‘N’ is not equal to 1. Inside the loop:
    • Check if the current number is already present in the hash set, if it is already present then it means a loop exists and we have to return “false”, and in case the current number is not present then insert it in the hash set.
    • Replace the current number with the next number, you may prefer using a separate function to do this.
  3. If the while loop ends, this means that the current number was equal to 1, and we will return “true” in this case.
Time Complexity

O( log ( N ) ), where N denotes the input integer.

 

Finding the next number if the current number is equal to N takes time of the order ~logN as we consider each digit of the current number and there are ~logN digits.

 

One can mathematically prove that the on average the number decreases logarithmically in each iteration, this leads to a total time complexity of O(logN) + O(log(logN)) + O(log(log(logN))) + …, here the O(logN) dominate the other terms.

Hence the time complexity is O( log(N) ).

Space Complexity

O( log ( N ) ), where N denotes the input integer.

 

In each iteration we are generating a new term and storing it in a hash-set, this new term is now almost logarithmically smaller than the previous term, one may mathematically prove that the terms generated in the worse case are of logarithmic order.

Hence the space complexity is O( log(N) ).

Code Solution
(100% EXP penalty)
Good Number
Full screen
Console