Skip to content
Related Articles

Related Articles

Minimum steps to reach Kaprekar’s Constant

View Discussion
Improve Article
Save Article
  • Last Updated : 06 Sep, 2022
View Discussion
Improve Article
Save Article

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 <bits/stdc++.h>
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
Recommended Articles
Page :

Start Your Coding Journey Now!