Minimum steps to reach Kaprekar’s Constant
Given a 4-digit number with at least two distinct digits, Your program should perform the following operations on the number:
- Arrange the digits in descending order and in ascending order.
- Subtract the smaller number from the bigger number.
- Repeat the above steps on the resultant number.
The task is to return the number of times these steps are repeated until 6174 is reached (6174 is the Kaprekar’s Constant).
- Performing the above steps will always cause you to reach a fixed number: 6174, and performing the routine on 6174 will always result in 6174 i.e., 7641 – 1467 = 6174.
- If a number is 3-digits or less then make it 4-digits by appending ‘0’ at the front.
- A number more than 4-digits is considered an invalid input.
5432 – 2345 = 3087
8730 – 0378 = 8352
8532 – 2358 = 6174.
2111-1112 = 999
9990-999 = 8991
9981-1899 = 8082
8820-288 = 8532
8532-2358 = 6174
Approach: The approach is based on simple deductive mathematics and string handling.
We just have to follow the above routine and create maximum and minimum if the inputs are valid in all cases. Otherwise, return -1 for invalids.
Follow the given steps to solve the problem:
- If the given number does not have at least two distinct digits or its length is greater than 4 when no routine has been applied on it then return “-1”. (isValid function checks for the frequency of the digits).
- If the number reaches 6174 then return the number of routines.
- Increment count of routines.
- If the length of the number is less than 4 then append ‘0’ at the front.
- Sort the resultant number in increasing and decreasing order.
- Calculate the difference between them.
- Call the function (recur) with the updated number and its length.
Below is the implementation for the above approach.
Time Complexity: O(1)
Auxiliary Space: O(1)
Why the complexity is constant?
Because we know that the number of recursions is always constant not going to be more than 7 for any valid input.