## Amazon Interview Question

Country: United States

Comment hidden because of low score. Click to expand.
3
of 3 vote

``````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;
}``````

Comment hidden because of low score. Click to expand.
0

what is the logic ?

Comment hidden because of low score. Click to expand.
0
of 0 vote

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 .

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0

for n= 2520, the smallest no whose digit's sum will be n is 5879 not 34567 as you suggested. Here is the explanation:
To get the smallest number, we divide the number with the greatest factor of the number which is less than 10, in this case it is 9, hence 9 is the last digit of the number. Remaining number is 2520/9=280. Now we divide 280 with the greatest factor of the number which is less than 10, which is 7. so second last digit of the required number is 7. Remaining number is 40. Again we divide 40 with 8, so the 3rd last digit is 8, remaining number is 5. As it is less than 10 so 5 is the first digit of the number. Hence the number comes out to be 5879.

Comment hidden because of low score. Click to expand.
0

*product(for n= 2520, the smallest no whose digit's product will be n is 5879 not 34567 )

Comment hidden because of low score. Click to expand.
0

@Isha, thanks for pointing that out. I missed a case there which is, 2*2*2=8.

So, my algorithm still works if I pick groups of factors using 2^3, 2^2, 2*3 or 3^2. Another plus point in using my algorithm is that I do not have to look for the largest factor of n which is less than 10. I can simply use the count of primes 2,3,5,7 to form the groups.

Comment hidden because of low score. Click to expand.
0

for n = 2540 ans is 5789
find the code below for correct answer.

Comment hidden because of low score. Click to expand.
0

You are almost there, the answer is 5789, to explain why you missed it:
You have to multiply all numbers (factors), where the result of the multiplication is less than 10.
So 2*2*2*3*5*7*3, is 2*2*2*3*3*5*7 = 4 * 2 * 9 * 5 * 7 = 8 * 9 * 5 * 7, sort in reverse and you have 5789.

Comment hidden because of low score. Click to expand.
0
of 2 vote

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 ....

Comment hidden because of low score. Click to expand.
0

and then we should multiply all 2's to make 4's and all 3's to make 9
if we have even of both(2's and 3's)---> do nothing
both odd----> multiply the remaining 2 and 3

and then sort to give the minimum number

Comment hidden because of low score. Click to expand.
0

@ phantom

lets take an example , say for number 4 find the lowest number so according to ur algo it should be 22 but there is number called 14 ;)

Comment hidden because of low score. Click to expand.
0
of 0 vote

#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={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;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#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={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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

int product()
{
int i,j,k, test, temp,temp1 = 1, remain, factor=0, found = 0;
int A={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
{
return -1;
}

return 0;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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());
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.