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).
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 = 6174Input: 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; } |
Java
/*package whatever //do not write package name here */ // java implementation import java.io.*; import java.util.*; public class GFG { public static int cnt = 0 ; // sort a string in ascending order public static String asc(String str) { char temp; char [] charArray = str.toCharArray(); for ( int i = 1 ; i < charArray.length; i++) { for ( int j = 0 ; j < charArray.length - 1 ; j++) { if (charArray[j] > charArray[j + 1 ]) { temp = charArray[j]; charArray[j] = charArray[j + 1 ]; charArray[j + 1 ] = temp; } } } return new String(charArray); } // sort a string on descending order public static String desc(String str) { char temp; char [] charArray = str.toCharArray(); for ( int i = 1 ; i < charArray.length; i++) { for ( int j = 0 ; j < charArray.length - 1 ; j++) { if (charArray[j] < charArray[j + 1 ]) { temp = charArray[j]; charArray[j] = charArray[j + 1 ]; charArray[j + 1 ] = temp; } } } return new String(charArray); } // Function to check for valid // input string once public static boolean isValid(String number, int n) { // Store each character in a set // unordered_set<char> freq; Set<Character> freq = new HashSet<Character>(); for ( int i = 0 ; i < n; i++) freq.add(number.charAt(i)); // Return false if all characters are // same else true return freq.size() >= 2 ? true : false ; } public static 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 (Integer.parseInt(number) == 6174 ) return cnt; // Count iterations cnt++; // If input string has less than 4 // characters insert '0' at the front while (n++ < 4 ) number = '0' + number.substring( 1 ); String number2 = number; // Sorting in ascending and descending // characters based on ASCII value number = asc(number); number2 = desc(number2); // Conversion from string to integer int increasing = Integer.parseInt(number); int decreasing = Integer.parseInt(number2); // Final calculation of bigger-smaller // number String resstr = Integer.toString(Math.abs(increasing - decreasing)); // If the 6174 is not reached yet, // then recur with updated string return noofRoutines(resstr, resstr.length()); } public static void main (String[] args) { String number = "9831" ; int n = number.length(); // Functions call System.out.println(noofRoutines(number, n)); } } // this code is contributed by ksam24000 |
Python3
# Python3 program to find No. of Routine # iterations to reach 6174 (Kaprekar Constant) # this program prints "-1" for invalid inputs def descOrder(s): str1 = ''.join( sorted (s,reverse = True )) return str (str1) # Function to check for valid # input string once def isValid(number,n): # Store each character in a set #unordered_set<char> freq; freq = {} freq = set () for i in range ( 0 ,n): freq.add(number[i]) # Return false if all characters are # same else true if ( len (freq)> = 2 ): return True return False def noofRoutines(number,n,cnt): # Base cases when length is more # than 4 or number does not have # at least two distinct digits if ((isValid(number, n) = = False or n > 4 ) and cnt = = 0 ): return - 1 elif ( int (number) = = 6174 ): return cnt # Count iterations cnt = cnt + 1 # If input string has less than 4 # characters insert '0' at the front while (n + 1 < 4 ): number[ 0 ] = '0' number2 = number # Sorting in ascending and descending # characters based on ASCII value res = ''.join( sorted (number)) number = res number2 = descOrder(number2) # Conversion from string to integer increasing = int (number) decreasing = int (number2) # Final calculation of bigger-smaller # number resstr = str ( abs (increasing - decreasing)) # If the 6174 is not reached yet, # then recur with updated string return noofRoutines(resstr, len (resstr),cnt) # Driver's code cnt = 0 number = "9831" n = len (number) # Functions call print (noofRoutines(number, n,cnt)) # This code is contributed by akashish__ |
C#
using System; using System.Collections.Generic; public class GFG { public static int cnt = 0; // sort a string in ascending order public static string asc( string str) { char temp; char [] charArray = str.ToCharArray(); for ( int i = 1; i < charArray.Length; i++) { for ( int j = 0; j < charArray.Length - 1; j++) { if (charArray[j] > charArray[j + 1]) { temp = charArray[j]; charArray[j] = charArray[j + 1]; charArray[j + 1] = temp; } } } return new string (charArray); } // sort a string on descending order public static string desc( string str) { char temp; char [] charArray = str.ToCharArray(); for ( int i = 1; i < charArray.Length; i++) { for ( int j = 0; j < charArray.Length - 1; j++) { if (charArray[j] < charArray[j + 1]) { temp = charArray[j]; charArray[j] = charArray[j + 1]; charArray[j + 1] = temp; } } } return new string (charArray); } // Function to check for valid // input string once public static bool isValid( string number, int n) { // Store each character in a set // unordered_set<char> freq; HashSet< char > freq = new HashSet< char >(); for ( int i = 0; i < n; i++) freq.Add(number[i]); // Return false if all characters are // same else true return freq.Count >= 2 ? true : false ; } public static 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 (Int16.Parse(number) == 6174) return cnt; // Count iterations cnt++; // If input string has less than 4 // characters insert '0' at the front while (n++ < 4) number = '0' + number.Substring(1); string number2 = number; // Sorting in ascending and descending // characters based on ASCII value number = asc(number); number2 = desc(number2); // Conversion from string to integer int increasing = Int16.Parse(number); int decreasing = Int16.Parse(number2); // Final calculation of bigger-smaller // number string resstr = Math.Abs(increasing - decreasing).ToString(); // If the 6174 is not reached yet, // then recur with updated string return noofRoutines(resstr, resstr.Length); } // Driver's code static public void Main() { string number = "9831" ; int n = number.Length; // Functions call Console.WriteLine(noofRoutines(number, n)); } } // This code is contributed by akashish__ |
Javascript
<script> // Javascript program to find No. of Routine // iterations to reach 6174 (Kaprekar Constant) // this program prints "-1" for invalid inputs let cnt = 0; // sort a string in ascending order function asc(str) { let temp; let charArray = Array.from(str); for (let i = 1; i < charArray.length; i++) { for (let j = 0; j < charArray.length - 1; j++) { if (charArray[j] > charArray[j + 1]) { temp = charArray[j]; charArray[j] = charArray[j + 1]; charArray[j + 1] = temp; } } } return charArray.join( "" ); } // sort a string on descending order function desc(str) { let temp; let charArray = Array.from(str); for (let i = 1; i < charArray.length; i++) { for (let j = 0; j < charArray.length - 1; j++) { if (charArray[j] < charArray[j + 1]) { temp = charArray[j]; charArray[j] = charArray[j + 1]; charArray[j + 1] = temp; } } } return charArray.join( "" ); } // Function to check for valid // input string once function isValid(number, n) { // Store each character in a set let freq = new Set(); for (let i = 0; i < n; i++) freq.add(number[i]); // Return false if all characters are // same else true return freq.size >= 2 ? 1 : 0; } function noofRoutines(number, 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 (parseInt(number) == 6174) return cnt; // Count iterations cnt++; // If input string has less than 4 // characters insert '0' at the front while (n++ < 4) number = '0' + number.substring(1); let number2 = number; // Sorting in ascending and descending // characters based on ASCII value number = asc(number); number2 = desc(number2); // Conversion from string to integer let increasing = parseInt(number); let decreasing = parseInt(number2); // Final calculation of bigger-smaller // number let resstr = Math.abs(increasing - decreasing).toString(); // If the 6174 is not reached yet, // then recur with updated string return noofRoutines(resstr, resstr.length); } // Driver's code let number = "9831" ; let n = number.length; // Functions call console.log(noofRoutines(number, n)); //This code is contributed by akashish__ </script> |
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.