Построить наименьшее число больше, чем K, используя только разрешенные цифры

Question

Дан массив, содержащий цифры между 0-9 и число K, найти наименьшее количество построенного цифр в массиве, таким образом, что она больше, чем K

Например, если array = [0,1] и K = 21, программа должна вернуть 100, так как 0, 1 и 10 меньше, чем 21 и 100 является первым числом, состоящим только из zeros и ones, который больше, чем 21.

Я могу думать о методе грубой силы, где я могу найти все возможные числа, которые могут быть созданы с цифрами в массиве, а затем найти наименьшее число, большее, чем K, но я ищу более умный и элегантный решение. Есть ли у вас какие-либо предложения?

Answer 1

Алгоритм:

Позвольте мне представить некоторые переменные:

k_digits - количество цифр в K.

Прежде всего, мы можем заметить, что наш итоговый номер будет иметь k_digits или k_digits + 1. Если еще не ясно, я объясню это более подробно в конце.

Начнем с предположения, что в ответе будут цифры k_digit.

Мы можем разделить нашу основную проблему на несколько меньших (а затем получить ответ на исходную проблему, объединив решения с подзадачами). Заявление подзадачи будет звучать следующим образом:

1. Какое наименьшее число больше, чем KБЕЗ последней цифры.
2. Можем ли мы составить число K без последней цифры из цифр, которые нам разрешено использовать?

Предположим, у нас есть решение этой проблемы. Тогда нам нужно найти ответ на начальную задачу. Мы можем сделать это следующим образом:

a) Если ответ на подзадачу 2 верен (мы можем составить без последней цифры). Затем мы должны попытаться добавить наименьшую доступную цифру из набора в конец этого номера, чтобы она была больше K. Что мы на самом деле делаем - мы пытаемся заменить последнюю цифру начального K на большую цифру от allowed set. Назовем это новый номерanswer1.

b) Добавить наименьший доступный номер из набора в конец номера из первой подзадачи. Это число будет больше, чем K, поскольку его префикс больше. Назовем это число answer2.

с) На заключительном этапе мы должны сравнить answer1 (если она существует) и answer2, и выбрать наименьшее. Это будет ответ на первоначальный вопрос.

Ну, теперь я надеюсь, что ясно, как мы комбинируем ответ из подзадач. Итак, теперь я объясню, как найти решение подзадач.

Начнем с второй подзадачи. Это легко - мы просто проверяем, есть ли у нас в наших allowed set все цифры номера K (без последнего).

Теперь первая подзадача. Вы можете заметить, что эта подзадача равна начальной задаче, но с меньшим K. Таким образом, мы можем решить эту проблему «рекурсивно». В базовом случае здесь будет однозначный K. Мы можем сказать ответ напрямую, когда у нас есть только одна цифра - просто для поиска нашего набора для цифры, большей цифры K.

Также обратите внимание, что в какой-то момент у нас может не быть ответа на подзадачу 1. Это означает, что мы не можем составить число длины k_digits, которое больше K. Но в этом случае мы всегда можем составить число с k_digits + 1. Просто выберите наименьшую цифру из разрешенного набора (k_digits + 1) раз. Специальный чехол: нули.

Пример:

allowed_set=[4,5] 
K = 435 

Мы можем видеть, что мы можем плюнуть нашу исходную задачу к подзадачи, где K = 43. Решение второй подзадачи будет false, так как нам не разрешено использовать цифру 3. Решение первой подзадачи мы попытаемся найти следующим образом - снова разбивая ее на две подзадачи, где K = 4. В этом случае ответ на первую подзадачу будет 5, а второй подзадаче будет 4. Мы можем составить ответ на случай K = 43 следующим образом: answer1 = 44, answer2 = 54. answer1 меньше, поэтому на самом деле это ответ на случай, когда K = 43. Затем, чтобы найти ответ для K = 435, мы можем добавить 4 в конец 44. Итак, ответ 444.

Это может быть не лучший пример, но я надеюсь, что это иллюстрирует мой ответ. Спросите, есть ли у вас дополнительные комментарии.

Answer 2

Можете ли вы построить число, равное данному, за исключением последней цифры, которая больше, да?

Нет ?, то можете ли вы построить число, равное данному, за исключением того, что десятки цифр больше?

Etc ...

Answer 3

Я совершенно новый в программировании, около 4 месяцев опыта работы с C++, и нам было предоставлено задание, очень похожее на это, как на одну из наших проблем с домашней работой, надеюсь, что это поможет!

//given array A of usable digits and assuming it is sorted 
//meaning A[1] is the smallest 

ans = 0; 

//first we find the digits of K 
//we use {} as Gauss 
K_digits = {log(K)} + 1 
numleft = K; 
for i = 1 to K_digits 
    B[i] = {numleft/(10^(K_digits - i))} 
    numleft = numleft - B[i]*10^(K_digits - i) 

//next we search through the array K_digits times 
Max_seq = A[A.length] // max number in array 
min_seq = A[1] // min number in array 
usebigger = 0 // if this equals 1, we need to add an extra digit than K to be larger than K 
copy = 0 //number of digits to copy, starting from left side 

j = 1 
while (j <= K_digits) 
    if Max_seq < B[j] 
     usebigger = 1 
     j = K_digits + 1 // end while loop 
    else if Max_seq == B[j] 
     copy = copy + 1 
     j = j + 1 
    else if Max_seq > B[j] 
     for t = 1 to A.length 
      if B[j] < A[t] 
      value = A[t] 
      break; 
     j = K_digits + 1 

if copy == K_digits // can only manage to find a same valued number 
    usebigger = 1 


//finally, with this info, we find the answer 
if usebigger == 1 // need to add an extra digit than K to be larger than K 
    if min_seq == 0 
     for s = 1 to A.length 
      if A[s] > 0 
      min_num = A[S] 
      break; 
     ans = min_num*(10^K_digits) 
    else 
     for x = 0 to K_digits 
      ans = ans + min_seq*(10^x)  

else 
    if copy != 0 
     for i = 1 to copy 
      ans = ans + B[i]*(10^(K_digits - i)) 
    ans = ans + value*(10^(K_digits - copy - 1)) 

    if copy+2 <= K_digits 
     for y = copy+2 to K_digits 
      ans = ans + min_seq*(10^(K_digits - y)) 

return ans