Last Updated: 5 Dec, 2021
Good Number
Moderate
Asked in companies
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.
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
Approaches
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 :
- Declare a hash set ‘hashSet’ to store all the numbers generated so far.
- 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.
- If the while loop ends, this means that the current number was equal to 1, and we will return “true” in this case.
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 some cycle finding algorithm to find if a loop exists, Floyd's Cycle-Finding Algorithm is a commonly used algorithm where we consider two pointers, a slow pointer which takes one step at a time and a fast pointer which takes two steps at a time, and according to this algorithm if a cycle exists then both the slow and fast pointers point to the same element after some finite iterations, you may read about this algorithm or you may just try the above-discussed logic to take an intuition of it. The benefit of using this method is that we now no longer need extra space to store all the generated elements in a hash-set.
The steps are as follows :
- Declare two pointers, ‘slow’ and ‘fast’, the first pointer corresponds to the slow-moving pointer and the other one corresponds to the fast-moving pointer.
- Initialize ‘slow’ to store the next number formed from the input ‘N’.
- Initialize ‘fast’ to store the next to the next number formed from the input ‘N’. Prefer using a separate function to find the next number of any given number, as this will help us to reduce duplication of the code to a large extent.
- Run a while loop till ‘slow’ is not equal to ‘fast’, this will help us find a cycle if it exists, inside the while loop:
- Update ‘slow’ to store the next number formed from the current number.
- Update ‘fast’ to store the next to the next number formed from the current number.
- Loop will end when both the pointers point to the same value, if this value is not equal to 1, then it means a loop was present and we will return “false” in this case.
- If both the pointers are equal to 1 at the end then it means the input number was a good number, and we will return “true” for this case.