Append Sort

Design a hardware module for the Append Sort problem.

Given a sequence of positive integers x, make the sequence strictly increasing from left to right. For each element, you may append zero or more decimal digits to the end of that element, but you may not change any existing digit.

Return the minimum total number of appended digits needed.

Hardware I/O Encoding

• x is a one-dimensional stream of unsigned 14-bit integers
• the stream order is the original array order
• the stream contains between 1 and 15 values
• each input value is in the range 1 to 16383
• the output is one unsigned 32-bit integer
• the output value is the minimum total number of appended decimal digits required

These bounds ensure every valid transformed value fits within 64-bit intermediate state.

Examples

Example 1

• input x = [100, 7, 10]
• output: 4

One optimal transformation is [100, 700, 1000], which appends 2 digits to 7 and 2 digits to 10.

Example 2

• input x = [9, 9]
• output: 1

The second value can become 90 by appending one digit.

Example 3

• input x = [1, 2, 3, 4]
• output: 0

The sequence is already strictly increasing.

Source: Google Code Jam 2021 Round 1A - Append Sort