Find the smallest number whose digits multiply to a given number n | GeeksforGeeks

Given a number ‘n’, find the smallest number ‘p’ such that if we multiply all digits of ‘p’, we get ‘n’. The result ‘p’ should have minimum two digits.

Case 1: n < 10 When n is smaller than n, the output is always n+10. For example for n = 7, output is 17. For n = 9, output is 19.

Case 2: n >= 10 Find all factors of n which are between 2 and 9 (both inclusive). The idea is to start searching from 9 so that the number of digits in result are minimized. For example 9 is preferred over 33 and 8 is preferred over 24.
Store all found factors in an array. The array would contain digits in non-increasing order, so finally print the array in reverse order.

void findSmallest(int n)

{

    int i, j=0;

    int res[MAX]; // To sore digits of result in reverse order

 

    // Case 1: If number is smaller than 10

    if (n < 10)

    {

        printf("%d", n+10);

        return;

    }

 

    // Case 2: Start with 9 and try every possible digit

    for (i=9; i>1; i--)

    {

        // If current digit divides n, then store all

        // occurrences of current digit in res

        while (n%i == 0)

        {

            n = n/i;

            res[j] = i;

            j++;

        }

    }

 

    // If n could not be broken in form of digits (prime factors of n

    // are greater than 9)

    if (n > 10)

    {

        printf("Not possible");

        return;

    }

 

    // Print the result array in reverse order

    for (i=j-1; i>=0; i--)

        printf("%d", res[i]);

}

Read full article from Find the smallest number whose digits multiply to a given number n | GeeksforGeeks