# Minimum steps to reach Kaprekar’s Constant

• Last Updated : 06 Sep, 2022

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).

Note:

• 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.

Examples:

Input: 3524
Output: 3
Explanation:
5432 – 2345 = 3087
8730 – 0378 = 8352
8532 – 2358 = 6174.

Input: 2111
Output: 5
Explanation:
2111-1112 = 999
9990-999 = 8991
9981-1899 = 8082
8820-288 = 8532
8532-2358 = 6174

Input: 9831
Output: 7

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.

## C++14

 `// C++ program to find No. of Routine``// iterations to reach 6174 (Kaprekar Constant)``// this program prints "-1" for invalid inputs``#include ``using` `namespace` `std;``int` `cnt = 0;`` ` `// Function to check for valid``// input string once``bool` `isValid(string& number, ``int``& n)``{`` ` `    ``// Store each character in a set``    ``unordered_set<``char``> freq;`` ` `    ``for` `(``int` `i = 0; i < n; i++)``        ``freq.insert(number[i]);`` ` `    ``// Return false if all characters are``    ``// same else true``    ``return` `freq.size() >= 2 ? 1 : 0;``}`` ` `int` `noofRoutines(string number, ``int` `n)``{`` ` `    ``// Base cases when length is more``    ``// than 4 or number does not have``    ``// at least two distinct digits``    ``if` `((!isValid(number, n) || n > 4) && cnt == 0)``        ``return` `-1;``    ``else` `if` `(stoi(number) == 6174)``        ``return` `cnt;`` ` `    ``// Count iterations``    ``cnt++;`` ` `    ``// If input string has less than 4``    ``// characters insert '0' at the front``    ``while` `(n++ < 4)``        ``number.insert(0, ``"0"``);`` ` `    ``string number2 = number;`` ` `    ``// Sorting in ascending and descending``    ``// characters based on ASCII value``    ``sort(number.begin(), number.end());``    ``sort(number2.begin(), number2.end(), greater<``int``>());`` ` `    ``// Conversion from string to integer``    ``int` `increasing = stoi(number);``    ``int` `decreasing = stoi(number2);`` ` `    ``// Final calculation of bigger-smaller``    ``// number``    ``string resstr = to_string(``abs``(increasing - decreasing));`` ` `    ``// If the 6174 is not reached yet,``    ``// then recur with updated string``    ``return` `noofRoutines(resstr, resstr.length());``}`` ` `// Driver's code``int` `main()``{``    ``string number = ``"9831"``;``    ``int` `n = number.length();`` ` `    ``// Functions call``    ``cout << noofRoutines(number, n);`` ` `    ``return` `0;``}`

Output

`7`

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.

My Personal Notes arrow_drop_up