Problem

The number 6174 is known as Kaprekar’s constant, after the mathematician who discovered an associated property: for all four-digit numbers with at least two distinct digits, repeatedly applying a simple procedure eventually results in this value. The procedure is as follows:

  • For a given input x, create two new numbers that consist of the digits in x in ascending and descending order.
  • Subtract the smaller number from the larger number.

For example, this algorithm terminates in three steps when starting from 1234:

  • 4321 - 1234 = 3087
  • 8730 - 0378 = 8352
  • 8532 - 2358 = 6174

Write a function that returns how many steps this will take for a given input N.

Examples

Example 1

1
2
3
4
5
6
7

Input: 1234
Output: 3
Explanation: Starting from 1234:
Step 1: 4321 - 1234 = 3087
Step 2: 8730 - 0378 = 8352  
Step 3: 8532 - 2358 = 6174
It takes 3 steps to reach Kaprekar's constant.

Example 2

1
2
3

Input: 6174
Output: 0
Explanation: The input is already Kaprekar's constant, so no steps are needed.

Example 3

1
2
3
4
5
6
7
8

Input: 1001
Output: 4
Explanation: Starting from 1001:
Step 1: 1100 - 0011 = 1089
Step 2: 9810 - 0189 = 9621
Step 3: 9621 - 1269 = 8352
Step 4: 8532 - 2358 = 6174
It takes 4 steps to reach Kaprekar's constant.

Example 4

1
2
3
4
5
6
7

Input: 5432
Output: 3
Explanation: Starting from 5432:
Step 1: 5432 - 2345 = 3087
Step 2: 8730 - 0378 = 8352
Step 3: 8532 - 2358 = 6174
It takes 3 steps to reach Kaprekar's constant.

Example 5

1
2
3

Input: 1111
Output: -1
Explanation: All digits are the same, so the procedure would result in 0000, which doesn't lead to Kaprekar's constant. Return -1 for invalid inputs.

Solution

Method 1 - Iterative Simulation

Intuition

We simulate the Kaprekar process by repeatedly sorting the digits in ascending and descending order, computing their difference, and counting steps until we reach 6174. We need to handle the number as a 4-digit string to preserve leading zeros.

Approach

  1. Convert the input number to a 4-digit string (pad with leading zeros if necessary)
  2. Check if all digits are the same - if so, return -1 as this won’t reach 6174
  3. Repeat the following until we reach 6174:
    • Sort digits in ascending order to get the smaller number
    • Sort digits in descending order to get the larger number
    • Subtract smaller from larger
    • Increment step counter
    • Convert result back to 4-digit string for next iteration
  4. Return the number of steps taken

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

class Solution {
public:
    int kaprekarSteps(int n) {
        string num = to_string(n);
        // Pad with leading zeros to make it 4 digits
        while (num.length() < 4) {
            num = "0" + num;
        }
        
        // Check if all digits are the same
        if (allSameDigits(num)) {
            return -1;
        }
        
        int steps = 0;
        int current = stoi(num);
        
        while (current != 6174) {
            string digits = to_string(current);
            while (digits.length() < 4) {
                digits = "0" + digits;
            }
            
            // Create ascending and descending numbers
            string asc = digits, desc = digits;
            sort(asc.begin(), asc.end());
            sort(desc.begin(), desc.end(), greater<char>());
            
            int smaller = stoi(asc);
            int larger = stoi(desc);
            
            current = larger - smaller;
            steps++;
            
            // Safety check to prevent infinite loop
            if (steps > 10) break;
        }
        
        return current == 6174 ? steps : -1;
    }
    
private:
    bool allSameDigits(const string& num) {
        for (int i = 1; i < num.length(); i++) {
            if (num[i] != num[0]) return false;
        }
        return true;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

import (
    "sort"
    "strconv"
    "strings"
)

func kaprekarSteps(n int) int {
    // Convert to 4-digit string
    num := strconv.Itoa(n)
    for len(num) < 4 {
        num = "0" + num
    }
    
    // Check if all digits are the same
    if allSameDigits(num) {
        return -1
    }
    
    steps := 0
    current := n
    
    for current != 6174 {
        // Convert to 4-digit string
        digits := strconv.Itoa(current)
        for len(digits) < 4 {
            digits = "0" + digits
        }
        
        // Create ascending and descending numbers
        asc := sortString(digits, true)
        desc := sortString(digits, false)
        
        smaller, _ := strconv.Atoi(asc)
        larger, _ := strconv.Atoi(desc)
        
        current = larger - smaller
        steps++
        
        // Safety check
        if steps > 10 {
            break
        }
    }
    
    if current == 6174 {
        return steps
    }
    return -1
}

func allSameDigits(num string) bool {
    for i := 1; i < len(num); i++ {
        if num[i] != num[0] {
            return false
        }
    }
    return true
}

func sortString(s string, ascending bool) string {
    chars := strings.Split(s, "")
    if ascending {
        sort.Strings(chars)
    } else {
        sort.Sort(sort.Reverse(sort.StringSlice(chars)))
    }
    return strings.Join(chars, "")
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

class Solution {
    public int kaprekarSteps(int n) {
        String num = String.format("%04d", n);
        
        // Check if all digits are the same
        if (allSameDigits(num)) {
            return -1;
        }
        
        int steps = 0;
        int current = n;
        
        while (current != 6174) {
            String digits = String.format("%04d", current);
            
            // Create ascending and descending numbers
            char[] ascChars = digits.toCharArray();
            char[] descChars = digits.toCharArray();
            
            Arrays.sort(ascChars);
            Arrays.sort(descChars);
            
            String asc = new String(ascChars);
            String desc = new StringBuilder(new String(descChars)).reverse().toString();
            
            int smaller = Integer.parseInt(asc);
            int larger = Integer.parseInt(desc);
            
            current = larger - smaller;
            steps++;
            
            // Safety check
            if (steps > 10) break;
        }
        
        return current == 6174 ? steps : -1;
    }
    
    private boolean allSameDigits(String num) {
        for (int i = 1; i < num.length(); i++) {
            if (num.charAt(i) != num.charAt(0)) {
                return false;
            }
        }
        return true;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

class Solution:
    def kaprekar_steps(self, n: int) -> int:
        # Convert to 4-digit string
        num = f"{n:04d}"
        
        # Check if all digits are the same
        if self._all_same_digits(num):
            return -1
        
        steps = 0
        current = n
        
        while current != 6174:
            # Convert to 4-digit string
            digits = f"{current:04d}"
            
            # Create ascending and descending numbers
            asc = ''.join(sorted(digits))
            desc = ''.join(sorted(digits, reverse=True))
            
            smaller = int(asc)
            larger = int(desc)
            
            current = larger - smaller
            steps += 1
            
            # Safety check
            if steps > 10:
                break
        
        return steps if current == 6174 else -1
    
    def _all_same_digits(self, num: str) -> bool:
        return all(digit == num[0] for digit in num)

Complexity

  • ⏰ Time complexity: O(k), where k is the number of steps (typically ≤ 7 for valid inputs). Each step involves sorting 4 digits which is O(1)
  • 🧺 Space complexity: O(1), only using constant extra space for string manipulations

Method 2 - Optimized with Cycle Detection

Intuition

We can optimize by detecting if we enter a cycle that doesn’t include 6174, which would indicate an invalid input. We also use more efficient digit manipulation without string conversions.

Approach

  1. Use a set to track visited numbers and detect cycles
  2. Extract digits using mathematical operations instead of string manipulation
  3. Sort digits using counting sort (since we only have 4 digits)
  4. Continue until we reach 6174 or detect a cycle
  5. Return steps if successful, -1 if we detect a cycle without reaching 6174

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

class Solution {
public:
    int kaprekarSteps(int n) {
        // Check for invalid input (all same digits)
        if (allSameDigits(n)) {
            return -1;
        }
        
        unordered_set<int> visited;
        int steps = 0;
        int current = n;
        
        while (current != 6174) {
            if (visited.count(current)) {
                return -1; // Cycle detected
            }
            visited.insert(current);
            
            vector<int> digits = extractDigits(current);
            
            // Sort for ascending and descending
            vector<int> asc = digits, desc = digits;
            sort(asc.begin(), asc.end());
            sort(desc.begin(), desc.end(), greater<int>());
            
            int smaller = digitsToNumber(asc);
            int larger = digitsToNumber(desc);
            
            current = larger - smaller;
            steps++;
        }
        
        return steps;
    }
    
private:
    vector<int> extractDigits(int num) {
        vector<int> digits(4, 0);
        for (int i = 3; i >= 0; i--) {
            digits[i] = num % 10;
            num /= 10;
        }
        return digits;
    }
    
    int digitsToNumber(const vector<int>& digits) {
        int result = 0;
        for (int digit : digits) {
            result = result * 10 + digit;
        }
        return result;
    }
    
    bool allSameDigits(int num) {
        vector<int> digits = extractDigits(num);
        for (int i = 1; i < 4; i++) {
            if (digits[i] != digits[0]) return false;
        }
        return true;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

func kaprekarStepsOptimized(n int) int {
    // Check for invalid input
    if allSameDigitsInt(n) {
        return -1
    }
    
    visited := make(map[int]bool)
    steps := 0
    current := n
    
    for current != 6174 {
        if visited[current] {
            return -1 // Cycle detected
        }
        visited[current] = true
        
        digits := extractDigits(current)
        
        // Sort for ascending and descending
        asc := make([]int, 4)
        desc := make([]int, 4)
        copy(asc, digits)
        copy(desc, digits)
        
        sort.Ints(asc)
        sort.Sort(sort.Reverse(sort.IntSlice(desc)))
        
        smaller := digitsToNumber(asc)
        larger := digitsToNumber(desc)
        
        current = larger - smaller
        steps++
    }
    
    return steps
}

func extractDigits(num int) []int {
    digits := make([]int, 4)
    for i := 3; i >= 0; i-- {
        digits[i] = num % 10
        num /= 10
    }
    return digits
}

func digitsToNumber(digits []int) int {
    result := 0
    for _, digit := range digits {
        result = result*10 + digit
    }
    return result
}

func allSameDigitsInt(num int) bool {
    digits := extractDigits(num)
    for i := 1; i < 4; i++ {
        if digits[i] != digits[0] {
            return false
        }
    }
    return true
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

class Solution {
    public int kaprekarSteps(int n) {
        // Check for invalid input
        if (allSameDigits(n)) {
            return -1;
        }
        
        Set<Integer> visited = new HashSet<>();
        int steps = 0;
        int current = n;
        
        while (current != 6174) {
            if (visited.contains(current)) {
                return -1; // Cycle detected
            }
            visited.add(current);
            
            int[] digits = extractDigits(current);
            
            // Sort for ascending and descending
            int[] asc = digits.clone();
            int[] desc = digits.clone();
            
            Arrays.sort(asc);
            Arrays.sort(desc);
            reverseArray(desc);
            
            int smaller = digitsToNumber(asc);
            int larger = digitsToNumber(desc);
            
            current = larger - smaller;
            steps++;
        }
        
        return steps;
    }
    
    private int[] extractDigits(int num) {
        int[] digits = new int[4];
        for (int i = 3; i >= 0; i--) {
            digits[i] = num % 10;
            num /= 10;
        }
        return digits;
    }
    
    private int digitsToNumber(int[] digits) {
        int result = 0;
        for (int digit : digits) {
            result = result * 10 + digit;
        }
        return result;
    }
    
    private void reverseArray(int[] arr) {
        for (int i = 0; i < arr.length / 2; i++) {
            int temp = arr[i];
            arr[i] = arr[arr.length - 1 - i];
            arr[arr.length - 1 - i] = temp;
        }
    }
    
    private boolean allSameDigits(int num) {
        int[] digits = extractDigits(num);
        for (int i = 1; i < 4; i++) {
            if (digits[i] != digits[0]) return false;
        }
        return true;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

class Solution:
    def kaprekar_steps(self, n: int) -> int:
        # Check for invalid input
        if self._all_same_digits_int(n):
            return -1
        
        visited = set()
        steps = 0
        current = n
        
        while current != 6174:
            if current in visited:
                return -1  # Cycle detected
            visited.add(current)
            
            digits = self._extract_digits(current)
            
            # Sort for ascending and descending
            asc = sorted(digits)
            desc = sorted(digits, reverse=True)
            
            smaller = self._digits_to_number(asc)
            larger = self._digits_to_number(desc)
            
            current = larger - smaller
            steps += 1
        
        return steps
    
    def _extract_digits(self, num: int) -> List[int]:
        digits = [0] * 4
        for i in range(3, -1, -1):
            digits[i] = num % 10
            num //= 10
        return digits
    
    def _digits_to_number(self, digits: List[int]) -> int:
        result = 0
        for digit in digits:
            result = result * 10 + digit
        return result
    
    def _all_same_digits_int(self, num: int) -> bool:
        digits = self._extract_digits(num)
        return all(digit == digits[0] for digit in digits)

Complexity

  • ⏰ Time complexity: O(k), where k is the number of steps until reaching 6174 or detecting a cycle. Each iteration is O(1) since we’re working with fixed 4 digits
  • 🧺 Space complexity: O(k), for storing visited numbers in the set to detect cycles