Отправлено: 19.06.18 16:17. Заголовок: Построение наименьшего числа из цифр заданного числа без использования массива.

Вот еще одна интересная задача на работу с числами, то есть на преобразование чисел без использования массивов, встреченная мною на сайте Stackoverflow

Forming the smallest number-

Требуется по заданному числу построить новое число таким образом, чтобы в нем не повторялись одинаковые цифры исходного числа, и при этом полученное число, состоящее из уникальных цифр исходного числа, было минимальным. При этом нельзя использовать массивы. А это означает, что нельзя также использовать строки.

Опять-таки, эта задача была задана на интервью.

Как я уже писал в другой теме, никогда не делайте никаких тестовых заданий на интервью. Интервью - это беседа, а не экзамен. То есть не позволяйте манипулировать вами и распоряжаться вашим временем по прихоти кого-либо.

Но вернемся к самой задаче.

Напрашивается подход к решению задачи с использованием сортировки вставкой, где сортируемыми элементами являются цифры числа. То есть для каждой цифры исходного числа нужно пройтись по цифрам формируемого числа и найти в формируемом числе позицию, куда надо вставить заданную цифру при условии, что в формируемом числе эта цифра пока еще отсутствует.

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

 
 #include <stdio.h> 
 #include <stdlib.h> 
  
 unsigned long long int smallest_unique_number( unsigned long long int n ) 
 { 
     const unsigned long long int Base = 10; 
      
     unsigned long long int m = 0; 
      
     do 
     { 
         unsigned long long int digit = n % Base; 
          
         if ( digit ) 
         { 
             unsigned long long int i = 1; 
             unsigned long long int numer, denom; 
              
             while ( numer = m / i, denom = m % i, numer != 0 && digit < numer % Base ) i *= Base; 
              
             if ( numer % Base < digit ) 
             { 
                 numer = numer * Base + digit; 
                 m = numer * i + denom; 
             } 
         } 
     } while ( n /= Base ); 
      
     return m; 
 } 
  
 int main( void ) 
 { 
     while ( 1 ) 
     { 
         printf( "Enter a non-negative number (0 - exit): " ); 
          
         unsigned long long n; 
          
         if ( scanf( "%llu", &n ) != 1 || n == 0 ) break; 
          
         printf( "\nThe smallest unique number formed from %llu is %llu\n\n", n, smallest_unique_number( n ) ); 
     } 
      
     printf( "\nThe smallest unique number formed from %llu is %llu\n\n", 0llu, smallest_unique_number( 0llu ) ); 
 } 
 

Вывод программы на консоль может выглядеть, например, следующим образом

 
 Enter a non-negative number (0 - exit): 1 
  
 The smallest unique number formed from 1 is 1 
  
 Enter a non-negative number (0 - exit): 2 
  
 The smallest unique number formed from 2 is 2 
  
 Enter a non-negative number (0 - exit): 10 
  
 The smallest unique number formed from 10 is 1 
  
 Enter a non-negative number (0 - exit): 11 
  
 The smallest unique number formed from 11 is 1 
  
 Enter a non-negative number (0 - exit): 13 
  
 The smallest unique number formed from 13 is 13 
  
 Enter a non-negative number (0 - exit): 132 
  
 The smallest unique number formed from 132 is 123 
  
 Enter a non-negative number (0 - exit): 991233612 
  
 The smallest unique number formed from 991233612 is 12369 
  
 Enter a non-negative number (0 - exit): 0 
  
 The smallest unique number formed from 0 is 0