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.
Read full article from 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.
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]);
}