Kaprekar's Constant

6174 is known as Kaprekar's constant, and was the subject of today's Daily Coding Challenge.

The number 6174 is known as Kaprekar's contant, 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.

Understanding the problem

Kaprekar's Constant

Kaprekar's constant involves sorting the number in ascending and descending order and then subtracting the smallest from the biggest of the two sorted numbers. This process is repeated until you arrive at 6174

The solution to the problem is determining how many steps it takes.

As someone who is not familiar with Kaprekar's constant, it was quite easy for me to initially misunderstand the problem

  • This is not a problem that involves permutating the digits

Solving it

The process is quite straight forward -

  • Sort the number in descending and ascending order
  • Subtract the number
  • Increment a counter
  • Return the counter if the result is 6174 otherwise repeat this process until you get Kaprekar's constant

Improving it

It was very hard to think of a way to improve the above solution. Since the size of the number is fixed at 4 digits, sorting it is always at constant time. The number of steps it takes to arrive at the constant is not optimizable.

We could optimize on memory - using a single array with an additional carry-on variable, but any savings would be minimal