Maximum continuous achievable number

Question

The problem

Definitions

• Let's define a natural number N as a writable number (WN) for number set in M numeral system, if it can be written in this numeral system from members of U using each member no more than once. More strict definition of 'written': - here CONCAT means concatenation.
• Let's define a natural number N as a continuous achievable number (CAN) for symbol set in M numeral system if it is a WN-number for U and M and also N-1 is a CAN-number for U and M (Another definition may be N is CAN for U and M if all 0 .. N numbers are WN for U and M). More strict:

Issue

Let we have a set of S natural numbers: (we are treating zero as a natural number) and natural number M, M>1. The problem is to find maximum CAN (MCAN) for given U and M. Given set U may contain duplicates - but each duplicate could not be used more than once, of cause (i.e. if U contains {x, y, y, z} - then each y could be used 0 or 1 time, so y could be used 0..2 times total). Also U expected to be valid in M-numeral system (i.e. can not contain symbols 8 or 9 in any member if M=8). And, of cause, members of U are numbers, not symbols for M (so 11 is valid for M=10) - otherwise the problem will be trivial.

My approach

I have in mind a simple algorithm now, which is simply checking if current number is CAN via:

1. Check if 0 is WN for given U and M? Go to 2: We're done, MCAN is null
2. Check if 1 is WN for given U and M? Go to 3: We're done, MCAN is 0
3. ...

So, this algorithm is trying to build all this sequence. I doubt this part can be improved, but may be it can? Now, how to check if number is a WN. This is also some kind of 'substitution brute-force'. I have a realization of that for M=10 (in fact, since we're dealing with strings, any other M is not a problem) with PHP function:

//$mNumber is our N, $rgNumbers is our U
function isWriteable($mNumber, $rgNumbers)
{
   if(in_array((string)$mNumber, $rgNumbers=array_map('strval', $rgNumbers), true))
   {
      return true;
   }
   for($i=1; $i<=strlen((string)$mNumber); $i++)
   {
      foreach($rgKeys = array_keys(array_filter($rgNumbers, function($sX) use ($mNumber, $i)
      {
         return $sX==substr((string)$mNumber, 0, $i);
      })) as $iKey)
      {
         $rgTemp = $rgNumbers;
         unset($rgTemp[$iKey]);
         if(isWriteable(substr((string)$mNumber, $i), $rgTemp))
         {
            return true;
         }
      }
   }
   return false;
}

-so we're trying one piece and then check if the rest part could be written with recursion. If it can not be written, we're trying next member of U. I think this is a point which can be improved.

Specifics

As you see, an algorithm is trying to build all numbers before N and check if they are WN. But the only question is - to find MCAN, so, question is:

• May be constructive algorithm is excessive here? And, if yes, what other options could be used?
• Is there more quick way to determine if number is WN for given U and M? (this point may have no sense if previous point has positive answer and we'll not build and check all numbers before N).

Samples

U = {4, 1, 5, 2, 0}
M = 10

then MCAN = 2 (3 couldn't be reached)

U = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11}
M = 10

then MCAN = 21 (all before could be reached, for 22 there are no two 2 symbols total).

Answer 1

Hash the digit count for digits from 0 to m-1. Hash the numbers greater than m that are composed of one repeated digit.

MCAN is bound by the smallest digit for which all combinations of that digit for a given digit count cannot be constructed (e.g., X000,X00X,X0XX,XX0X,XXX0,XXXX), or (digit count - 1) in the case of zero (for example, for all combinations of four digits, combinations are needed for only three zeros; for a zero count of zero, MCAN is null). Digit counts are evaluated in ascending order.

Examples:

1. MCAN (10, {4, 1, 5, 2, 0})
   3 is the smallest digit for which a digit-count of one cannot be constructed.
   MCAN = 2

2. MCAN (10, {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11})
   2 is the smallest digit for which a digit-count of two cannot be constructed.
   MCAN = 21

3. (from Alma Do Mundo's comment below) MCAN (2, {0,0,0,1,1,1})
   1 is the smallest digit for which all combinations for a digit-count of four
   cannot be constructed.
   MCAN = 1110

4. (example from No One in Particular's answer) 
   MCAN (2, {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1111,11111111})
   1 is the smallest digit for which all combinations for a digit-count of five
   cannot be constructed.
   MCAN = 10101