CareerCup

int getnumber(int n)
{
    if(n==0|| n==1)
       return -1;
    int i=9;
    int num=0;
    int pow=1;
    while(i>0)
    {
        while(n%i==0 && i>1)
        {
           num=i*pow + num;
           pow=pow*10;
           n=n/i;
        }
        i--;
    }
    if(n!=1)
       return -1;
    return num;
}

I hav idea how to decide whether we can do it or not. We need to factorize number in prime factors. If among of themat least one prime that is greater than 10 - we cannot do it .

Factor n into primes (assuming n is not an RSA kind of number). The simplest and most obvious number whose digits multiply to give n is simply these primes concatenated.

However, we need to find the smallest number. So, for that we will need to multiply all pairs of 2's, 2's and 3's and pairs of 3's. This is because only these are less than 10: 2*2=4, 2*3=6, 3*3=9. Once, we have multiplied all such pairs, we just need to check for any primes > 7. If no such prime, we just arrange the digits in ascending order and get the smallest number.

example: lets say n=2520=2*2*2*3*5*7*3,
then we can group this as (2*2), (2*3), 5,7,3. Sort the digits to give 34567.

Instead of factoring the number, all we need to do, is to check whether the number can be formed by a combination of 2,3,5,7
(since no other prime number like 11,13 can be represented as a single digit)

So we go ahead , get the maximum power of 2 in the number, let's say w.
similarly we go ahead with 3,5 ,7 , and let's say we get x,y,z
and then if (2^w )*(3^x)*(5*y)(7^z) == number itself,
the smallest number would be
(2222....) w times ...(3333...) x times (5555....)y times (777...)z times

else print -1

Worst case time complexity - O(logn)

Wonder if we can optimize it further ....

#include <iostream>
#include <stdio.h>

int main()
{
int test;
scanf("%d",&test);

for(int i=0;i<test;i++)
{
long long int n;
scanf("%lld",&n);

int A[10]={0};

for(int j=9;j>0;j--)
{
if(n==1)
break;

while(n%j==0)
{
A[j]++;
n/=j;
}
}

if(n>1)
{
printf("-1\n");
continue;
}

for(int j=2;j<10;j++)
{
while(A[j]>0)
{
A[j]--;
printf("%d",j);
}
}
printf("\n");
}
return 0;
}

#include <iostream>
#include <stdio.h>

int main()
{
	int test;
	scanf("%d",&test);
	
	for(int i=0;i<test;i++)
	  {
	  	  long long int n;
	  	  scanf("%lld",&n);
	  	  
	  	  int A[10]={0};
	  	  
	  	  for(int j=9;j>0;j--)
	  	    {
	  	    	if(n==1)
	  	    	  break;
	  	    	  
	  	    	while(n%j==0)
	  	    	  {
	  	    	  	  A[j]++;
	  	    	  	  n/=j;
	  	    	  }
	  	    }
	  	    
	  	  if(n>1)
		    {
		    	printf("-1\n");
		    	continue;
		    }
			  
	  	  for(int j=2;j<10;j++)
			{
				while(A[j]>0)
				  {
				  	 A[j]--;
				  	 printf("%d",j);
				  }
			}  
	      printf("\n");		
	  }
return 0;	  
}

int product()
{
int i,j,k, test, temp,temp1 = 1, remain, factor=0, found = 0;
int A[10]={0};

printf("enter the number \n");
scanf("%d",&test);

temp = test;
i = 9;
j = 0;

while (i>= 2)
{
factor = 0;
while((temp%i == 0) && (temp > 0))
{
factor = 1;
A[j] = i;
printf("filling is A[%d] is %d \n", j,A[j]);
j++;
temp /= i;
}
temp1 = 1;
if (factor)
{
k = j-1;

for (; k>=0; k--)
{
printf("factor at A[%d] is %d \n", k,A[k]);
temp1 *= A[k];
if (temp1 == test)
{
printf("factor found %d \n", temp1);
found = 1;
break;
}
}
}

if (found)
break;
temp = test;
i--;

}

j--;

if (found)
{
for (; j>=0; j--)
{
printf("factor is A[%d] is %d \n", j,A[j]);
}
}else
{
printf("factor is not found \n");
return -1;
}

return 0;
}

This is the code I came up with, to print the smallest number with the digits product equal to the number.

int prod(int n, int res)
{
    if(res>n)
        return 0;
    else if(res==n)
    {
        return 1;
    }
    for(int i=9;i>2;i--) // we take i from 9 -> 2, since the o/p will be printed from last digit onwards so it will be the minimum no.
    {
        res*=i;  // multiply a digit
        if(prod(n,res)){
            cout<<i;
            return 1;
        }
        else
            res/=i;  // backtrack
    }
    return 0;
}
int main()
{
    prod(2520,1);
}

The number printed on the screen will be the result. For above case the o/p is 5789

public static int strip(int number) {

int divisor = 9;
StringBuilder min = new StringBuilder();

while(number != 1) {
if (number%divisor != 0) {
divisor--;
} else {
min.append("" + divisor);
number = number/divisor;
divisor = 9;
}
}

return Integer.parseInt(min.reverse().toString());
}

2580--->highest factor(between 10)=9
2580/9=280-->highest factor(between 10)=8
280/8=35-->highest factor(between 10)=7
35/7=5-->highest factor(between 10)=5
ans--->5789