## Amazon Interview Question for SDE1s

Country: India
Interview Type: In-Person

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

``````/*
* Given a number N,
* find the smallest 3 digits number such that product of its digits is equal to N.
* For example for N=100 , 3 digits number is 455.
*/

public class Min3DigtProdEqualN {

public int findMin3DigitNum(int givenN){

for(int i=100;i<1000;i++){
if(givenN==getProductOfDigits(i))
return i;

}

return -1;
}

public int getProductOfDigits(int num){

int product=1;
do{
int a=num%10;
product*=a;
num/=10;
}while(num>0);
return product;
}

}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

How to guarantee you get smallest 3 digits number?

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

Min could be guaranteed, i is in the increasing order and will be returned once i equals to the given N.

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

@praveenkcs28: what is the logic here?

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

Sweep for all digits. It takes much less than it looks like since not all digits divide N.

Test case for 27: answer 139

``````N = 27;
if N == 0:
print 100
exit()

for n in range(1, 10):
if N % n != 0:
continue
M = N / n
for m in range(1, 10):
if M % m != 0:
continue
L = M / m
if L < 10:
n = n * 100 + m * 10 + L
print n
exit()``````

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

won't it give bad output since N%n==0 for n=1, M%m=0 for m=1 and so on.

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

I guess not. It is possible that the digit is a one. E.g, N=1 leads to 111. If the first two picked digits are very small then L in the code above will be more than 9 which is not accepted. E.g N=27 by picking n=1 & m=1 L=27 and not accepted.

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

``````#include <iostream>
#include <cmath>
using namespace std;

int product(int N)
{
if(N/10 == 0)
return N;
else
return (N%10) * product(N/10);
}
int findMumber(int  N)
{
int digits = 0;
int temp = N;
while(temp = temp / 10 )
digits++;

int start = pow(10, digits);
int i = start + 1;
for (; ; ++i)
{
if (product(i) == N)
break;
}
return i;
}

int main()
{
cout<<findMumber(100)<<endl;``````

}

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

I am still yet to understand full how your code works， but I tested your code with numbers N < 100, and it didnt return 3 digits, instead, it returned only 2 digits. For instance, if N = 25, it would only return 55. I think the correct answer should be 5,5,1.

I also tried with N = 111, it runs forever into an endless loop, because there is no end condition -- 3 digits.

I dont fully understand the requirements: what 'smallest 3 digits' means. For instance, if N=144, so the answer should be (8,3,6), or (4,6,6), or?

I believe your algorithm works, but it can take long time/many loops to work out the digits. In fact, I dont even know how to estimate the worst case scenario. Do you?

One of the improvement to shorten the times to find these digits is to catalogue the number N before deciding what digit(s) to use the product. For instance, if N is an odd number, there is no point to use an even digit for producing the product, etc...

What do you think?

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

I think I understand what ''smallest 3 digits number' means...

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

``````public static void findThreeDigitNumber(int num)
{
int r=0;
if(num>=1)
{
for(int i=1;i<10;i++)
{
if(num % i==0)
{
int temp=num/i;
for(int j=1;j<10;j++)
{
if(temp%j==0 && temp/j<10)
{
r=(temp/j)*100+(j)*10+num/temp;
}
}
}
}}
System.out.println(r);
}``````

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

You are asuming that the input number is greater than or equal 100 which was not given.

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

``````/* accepts input for no of digits and the number for the product to be checked */

int main()
{
int digits,N,min;

digits = atoi(argv[1]); /* no of digits */
N = atoi(argv[2]); 	/* This the number to be checked for the product */

min = 1 << (digits -1 );
while ( min <  (1 << digits))
{
if ( N == product(N))
return min;
min++;
}
printf(" Product not present \n");

return 0;
}

int product (int n)
{
if ( n == 0)
return 1;
return((n % 10) * product(n/10));
}``````

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

find the product of smallest 3 digit number of the given number N.

/* accepts input for no of digits and the number for the product to be checked */

int main()
{
int digits,N,min=1;

digits = atoi(argv[1]); /* no of digits */
N = atoi(argv[2]); /* This the number to be checked for the product */

for(i=0; i< digits; min = min*10);
digits = min*10;
while (min < digits)
{
if ( N == product(min))
return min;
min++;
}
printf(" Product not present \n");

return 0;
}

int product (int n)
{
if ( n == 0)
return 1;
return((n % 10) * product(n/10));
}

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

I think it is all about getting the factors of the number N and then sort it in increasing order. Right now I am not able to think in which cases it won't work.

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

8 = 2*2*2, but correct answer would be 118.

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

``````find the product of smallest 3 digit number of the given number N.

/* accepts input for no of digits and the number for the product to be checked */

int main()
{
int digits,N,min=1;

digits = atoi(argv[1]); /* no of digits */
N = atoi(argv[2]); 	/* This the number to be checked for the product */

for(i=0; i< digits; min = min*10);
digits = min*10;
while (min < digits)
{
if ( N == product(min))
return min;
min++;
}
printf(" Product not present \n");

return 0;
}

int product (int n)
{
if ( n == 0)
return 1;
return((n % 10) * product(n/10));
}``````

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

``````public static  int? FindNumber (int input)

{
for (int i=1;i<10;i++)
{
if (input%i!=0)
continue;
int result = input/i;
for (int j=1;j<10;j++)
{
if (result %j!=0 || (result/j )>9)
continue;
int requiredNumber = result/j+j*10+i*100;
return requiredNumber;
}
}
//there is no solution
return null;
}``````

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

package assignment;
class Assignment {
public static void main(String[] args) {

int i=100;
while(i<1000)
{
System.out.println("2nd loop"+i);
int s=i;
int p=1;
while(i>0)
{
System.out.println("i="+i);
int n=i%10;
p=p*n;
i=i/10;
}
System.out.println(p);
if(p==Integer.parseInt(args[0]))
{
System.out.printf("Number is %d",s);
break ;
}
else
{
i=s+1;
System.out.println("i="+i);
}
}}}

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

e.g. 600
the factor of 600 is factorArray[] = {2,2,2,3,5,5}
first step multiply factorArray[len -2]factorArray[len -3] which is 2 and 3. then sort and get {2,2,5,5,6}
repeat above step {2,5,6,10} and then {6, 10, 10}

the answer is {6, 10, 10}

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

e.g. 600
the factor of 600 is factorArray[] = {2,2,2,3,5,5}
first step multiply factorArray[len -2]factorArray[len -3] which is 2 and 3. then sort and get {2,2,5,5,6}
repeat above step {2,5,6,10} and then {6, 10, 10}

the answer is {6, 10, 10}

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

the answer should be like 3 digit number like 123,457,568 and not like {10 10 6 }set.
for example 100 we can get 3 digit number like 455(4*5*5=100) not like 10 10 1 (10*10*1=100).

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

Let's try this efficient version:

``````#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int factor(int& n, int p)
{
int ret = 0;

while (n && n % p == 0) {
ret++;
n /= p;
}
return ret;
}

bool magic_number(int n)
{
// first decompose 'n' into 2^p2 3^p3 5^p5 7^p5
int p2 = factor (n, 2);
int p3 = factor (n, 3);
int p5 = factor (n, 5);
int p7 = factor (n, 7);

// if there are factors other than 2, 3, 5, 7, there's no solution
if (n != 1)
return false;

vector<int> v;

for (int i = 0; i < p7; i++)    // one factor of 7 needs one digit
v.push_back(7);

for (int i = 0; i < p5; i++)    // one factor of 5 needs one digit
v.push_back(5);

for (int i = 0; i < p3 / 2; i++)    // 2 factors of 3 can form one digit 9
v.push_back(9);

if (p3 % 2 && p2) {         // factor 2 and 3 can form one digit 6
v.push_back(6);
p2--;
}

for (int i = 0; i < p2 / 3; i++)  // 3 factors of 2 can form one digit 8
v.push_back(8);

p2 %= 3;

for (int i = 0; i < p2 / 2; i++)  // 2 factors of 2 can form one digit 4
v.push_back(4);

if (p2 % 2)                 // 1 factor of 2 can for one digit 2
v.push_back(2);

if (v.size() > 3)           // too many digits
return false;

int d = 3 - v.size();       // fill digit 1 if there are still spaces
for (int i = 0; i < d; i++)
v.push_back(1);

sort(v.begin(), v.end());
for(int i : v)
cout << i << " ";

cout << endl;
return true;
}

int main()
{
int n = 100;

magic_number(n);

return 0;
}``````

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

If we divide the number n by 9 ... 2 until n > 1 then we will get the smallest number

If n = 100 then
n / 9 = x
n / 8 = x
n / 7 = x
n / 6 = x
n / 5 = 10

now n = 10 then

n / 9 = x
n / 8 = x
n / 7 = x
n / 6 = x
n / 5 = 2

now n = 2 then

n / 9 = x
n / 8 = x
n / 7 = x
n / 6 = x
n / 5 = x
n / 4 = x
n / 3 = x
n / 2 = 1

2x5x5 = 100.
So, 255 is the smallest number.

If n = 12 then

n / 9 = x
n / 8 = x
n / 7 = x
n / 6 = 2

now n = 2

n / 9 = x
n / 8 = x
n / 7 = x
n / 6 = x
n / 5 = x
n / 4 = x
n / 3 = x
n / 2 = 1

so, 2 * 6 = 12. i.e. 1 x 2 x 6 = 12 that's why 126 is the smallest number

``````public class Smallest {
private static int[] min(int n) {
int[] x = new int[50];
int i = 0;
x[1] = x[2] = 1;
boolean isItNotDivisible = true;
while(n > 1){
isItNotDivisible = true;
int m = 9;
while(m > 1) {
if(n % m == 0) {
x[i++] = m;
n /= m;
isItNotDivisible = false;
break;
}
m--;
}
if(isItNotDivisible == true) {
x[0] = 0;
return x;
}
}

return x;
}
public static void main(String[] args) {
int[] x;
int n = 112;
x = min(n);
if(x[0] != 0 && x[3] == 0) {
System.out.print(x[2]);
System.out.print(x[1]);
System.out.print(x[0]);
}
}
}``````

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

@RiponCoder: would it work for 8?

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

``````if n = 8
x[1] = x[2] = 1;
while(n > 1){
int m = 9;
while(m > 1) {
if(n % m == 0) {
x[i++] = m;
n /= m;
}
m--;
}
}

x[0] = 8, x[1] = 1, x[2] = 1.

So, for 8 ans: x[2] x[1] x[0] = 118``````

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

This can be done using recursion as below.

``````void smallestNum(int N)
{
cout << endl << "In recursion N is:" << N <<endl;
int iQuotient;
static int i;
static int iSmallestNo[10] ;
bool isNotPrime = false;

for(int iDivisor=9;iDivisor > 1;iDivisor--)
{
if(!(N % iDivisor))
{
isNotPrime = true;
iQuotient = N/iDivisor;
cout << endl << "quotient is :"<<iQuotient;
cout << endl << "divisor is :" << iDivisor;
iSmallestNo[i] = iDivisor;
i++;
cout << endl << "w is :" << iSmallestNo;
if(iQuotient > 1)
smallestNum(iQuotient);

break;

}
}
int count = --i;
if(!(isNotPrime))
{
iSmallestNo[0] =  -1;
}
cout << "\n finally smallest number is :";
while(count>=0)
{
cout << iSmallestNo[count];
count--;
}
}``````

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

``````public int findThreeDigitNumber(int target) {
int maxDigit = 9;
int i
while (maxDigit > 0 && tempAnswer<100) {
if( (target%maxDigit) == 0) {
target /= maxDigit;
} else {
maxDigit--;
}
}
} else {
return -1;
}
}``````

after finding the biggest digit there is no need to check bigger digits.

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

step-1 : Divide the number with 9 to 2.
step-2: if a divisor is greater than 9, then solution is not possible
step-3: arrange the numbers in increasing order,
step-4: print the array
Ex: 100 (factors: 5,5,4)---> (4,5,5)

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

if N=120 then?

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

step-1 : Divide the number with 9 to 2.
step-2: if a divisor is greater than 9, then solution is not possible
step-3: arrange the numbers in increasing order,
step-4: print the array
Ex: 100 (factors: 5,5,4)---> (4,5,5)

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

``````bool dfs(int idx, int target, int product, vector<int>& buf){
if(idx == 3){
if(target == porduct) return true;
return false;
}
if(product > target) return false;
for(int i = 1; i < 10; i++){
buf.push_back(i);
bool b = dfs(idx+1, target, product*i, buf);
if(b) return true;
buf.pop_back();
}
return false;
}``````

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

Not a complete solution, just breaking the problem into reasonable parts
a) Prime factorize the given number 'N'
b) Put the factors in an array in ascending order
c) Aim to multiply the elements of the array in such a way that the result has just 3 elements in the array.

e.g N = 40
Factorization = 2,2,2,5
Array = 1,2,2,2,5
Possible combinations: 185, 245 -> 185->158 (By sorting in ascending order)

e.g N = 60
Factorization = 2,2,3,5
Array: 1,2,2,3,5
Possible combinations: 265, 435 -> 256 -> 256

Note: We can't combine any prime factor above 3 (i.e. 5,7) with any other prime factor since it would cause a two digit resultant. So, all we need to optimize is the product of factors of 2 and 3 only.

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

public static String solution(long givenN) {
List result = new ArrayList();
while (givenN > 1) {

int k = 9;
while (givenN % k > 0) {
k = k - 1;
}
if (k > 1) {
givenN /= k;
} else {
result.clear();
result.add("Cannot be written as a product of digits because "+givenN+" is a prime number");
break;
}
}
Collections.reverse(result);
StringBuilder sb = new StringBuilder();
for (Object o : result) {
sb.append(o);
}
return sb.toString();
}

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

pseudo code:

Find the smallest factors of N
e.g. N= 100 sorted array of factors = 2,2,5,5

Then club smallest factors to make a bigger factor starting from the beginning of the array till the array contains only 3 factors

i.e. sorted array of factors = (2*2),5,5 -> (4,5,5). By multiplying the digits by corresponding powers of 10 the output can be obtained.

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

if N=120 then?

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

``````#include<iostream>
#include<string>
#include<sstream>
#include<math.h>

bool isPrime(const int &x)
{
for(int i=2;i<sqrt(x);i++)
{
if(x%i==0)
return false;
}

return true;
}

int main()
{
int N = 100;
int out = 0;

for(int i=9;i>=2;i--)
{
if(N%i==0 && !isPrime(N/i))
{
out = i;
N = N/i;
break;
}
}

for(int i=9;i>=2;i--)
{
if(N%i==0 && isPrime(N/i))
{
out = out + (i*10);
out = out + ((N/i)*100);
break;
}

}

std::cout<<out<<std::endl;
}``````

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

public class HelloWorld{

public static void main(String []args){

int first=0,second=0,third=0;
int N=64;
int remainder=0;

for(int i=9;i>0;i--){

if(N%i==0){
first=i;
remainder=N/first;
break;
}

}
for(int i=first;i>0;i--){
if(remainder%i==0){
second=i;
remainder=remainder/second;
break;
}
}

for(int i=second;i>0;i--){
if(remainder%i==0){
third=i;
break;
}
}
System.out.println("Hello World "+third+second+first);

}
}

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

``````public class HelloWorld{

public static void main(String []args){

int first=0,second=0,third=0;
int N=64;
int remainder=0;

for(int i=9;i>0;i--){

if(N%i==0){
first=i;
remainder=N/first;
break;
}

}
for(int i=first;i>0;i--){
if(remainder%i==0){
second=i;
remainder=remainder/second;
break;
}
}

for(int i=second;i>0;i--){
if(remainder%i==0){
third=i;
break;
}
}
System.out.println("Hello World "+third+second+first);

}
}``````

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

Place your number in N and run the code... it works completely fine. 200%

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

Test for 99 ,999, 720

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

``````def find_dig_factor(n):
#Factors 2- 9, least number
i, factors=9, []
while True:
if not (n%i):
n= n/i
factors.append(i)
else:
i-=1
if n is 1:
break
elif i is 1:
return None

return int("".join(map (str, reversed(factors))))``````

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

// The program hasnt been thoroughly tested although basic cases have gone through;
// The 3 digits can only be 999 max;
// So use the biggest digit to divide the N (and its remaining) as earliest as possible to yield the possible 3 digit number as quickest as possible;
// Once we get the 3 digits, sort them to get the smallest number.
// Time and space: O(1), very limited extra space required
// Limitation: if the requirement is changed to 4 digits instead of 3, findNumber() needs written.
// The improvement for the function is to take only one digit to be sorted: findNumber(int & iN, int iTh, int &iDigit);
// so recursive can occur easily for any number of digits
// When iN = 0 or iN = 1, the function is quite clumsy although it works.
// I am sure the program can be improve a bit, but I am a bit numb at the moment.

#include <iostream>
using namespace std;

const int ci999 = 729;
const int ci99 = 81;
const int ci9 = 9;

int findNumber(int iN, int iNumDigit, int & iFirst, int & iSecond, int & iThird)
{
int iReturn = 0;

int iNumerator = 1;
if(iN == 0)
{
iReturn = iN;
}
else if(iN == 1)
{
if(iNumDigit == 3)
{
iFirst = 1;
iSecond = 1;
iThird = 1;
}
else
{
iReturn = iN;
}
}
else if(iN % 9 == 0)
{
iNumerator = 9;
}
else if(iN % 8 == 0)
{
iNumerator = 8;
}
else if(iN % 7 == 0)
{
iNumerator = 7;
}
else if(iN % 6 == 0)
{
iNumerator = 6;
}
else if(iN % 5 == 0)
{
iNumerator = 5;
}
else if(iN % 4 == 0)
{
iNumerator = 4;
}
else if(iN % 3 == 0)
{
iNumerator = 8;
}
else if(iN % 2 == 0)
{
iNumerator = 2;
}
else // 2/3 digit prime number
{
cout << "prime number" << endl;
iReturn = -1;
}

if(iReturn != -1 && iReturn != -2)
{
if(iNumDigit == 3)
{
iFirst = iNumerator;
iSecond = iN/iNumerator;

if(iSecond <= 9)
{
iThird = iFirst;
iFirst = 1;
}
else
{
iReturn = findNumber((iN/iNumerator), (iNumDigit - 1), iFirst, iSecond, iThird);
}
}
else if(iNumDigit == 2)
{
iSecond = iNumerator;
iThird = iN / iNumerator;
if(iThird > 9)
{
return -1;
}
}
}
return iReturn;
}

int findMin(int & iFirst, int & iSecond, int & iThird)
{
int iTmp = -1;
if(iFirst >= iSecond)
{
// 981
if(iSecond > iThird)
{
iTmp = iFirst;
iFirst = iThird;
iThird = iTmp;
}
else // 918
{
iTmp = iFirst;
iFirst = iSecond;
iSecond = iTmp;
}
}
// 891
if(iSecond > iThird)
{
iTmp = iSecond;
iSecond = iThird;
iThird = iTmp;
}
return 1;
}

int validate(int iN, int iNumDigit)
{
int iReturn = 0;
if((iN < 0)
||((iNumDigit == 3 && iN > ci999))
||(iNumDigit == 2 && iN > ci99)
||(iNumDigit == 1 && iN <= ci9))
{
iReturn = -1;
}
return iReturn;
}

int main()
{
int iN = 11;
int iFirst = 0;
int iSecond = 0;
int iThird = 0;

if(validate(iN, 3) == 0)
{
if(findNumber(iN, 3, iFirst, iSecond, iThird) == -1)
{
cout << iN << " doesnt have such a combination" << endl;
}
else
{
cout << "iN " << iN << " iFirst " << iFirst << " iSecond " << iSecond << " iThird " << iThird << endl;

findMin(iFirst, iSecond, iThird);

cout << "iN " << iN << " iFirst " << iFirst << " iSecond " << iSecond << " iThird " << iThird << endl;
}
}
else // iN is out of a valid range
{
cout << iN << " is out side of a valid range" << endl;
}

return 1;
}

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

``````int find_min(int n)
{
int i,j,k,pro=1,temp,temp2;
for(i=1;i<10;i++)
{
pro*=i;
for(j=0;j<10;j++)
{
temp=pro;
pro*=j;
for(k=0;k<10;k++)
{
temp2=pro;
pro*=k;
if(pro==n)
return (i*100+j*10+k);
pro=temp2;
}
pro=temp;
}
pro=1;
}
return -1;
}``````

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

int n = 100;
ArrayList<Integer> a = new ArrayList<Integer>();
for(int i= 1;i<10;i++)
{
if ((n%i)==0)

}
System.out.println(a);
for(int i = 0;i<a.size();i++)
{
for(int j=0;j<a.size();j++)
for(int k=0;k<a.size();k++)
{
if((a.get(i)*a.get(j)*a.get(k))==n)
System.out.println(a.get(i)+""+a.get(j)+""+a.get(k));

}

}

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

int n = 100;
ArrayList<Integer> a = new ArrayList<Integer>();
for(int i= 1;i<10;i++)
{
if ((n%i)==0)

}
System.out.println(a);
for(int i = 0;i<a.size();i++)
{
for(int j=0;j<a.size();j++)
for(int k=0;k<a.size();k++)
{
if((a.get(i)*a.get(j)*a.get(k))==n)
System.out.println(a.get(i)+""+a.get(j)+""+a.get(k));

}

}

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

{
int n = 100;
ArrayList<Integer> a = new ArrayList<Integer>();
for(int i= 1;i<10;i++)
{
if ((n%i)==0)

}
System.out.println(a);
for(int i = 0;i<a.size();i++)
{
for(int j=0;j<a.size();j++)
for(int k=0;k<a.size();k++)
{
if((a.get(i)*a.get(j)*a.get(k))==n)
System.out.println(a.get(i)+""+a.get(j)+""+a.get(k));

}

}
}

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

Here's an idea:

Initialize m to n and initialize an empty integer stack: mul.
Iterate from 9 to 1 and do the following:
while m divides i (i is the current iteration value) push i into the mul stack and divide m by i.

Stop each of the loops above if the number of elements in the stack is equal to 3. Notice that the mul stack will contain digits in an increasing order (from the head) whose multiplication is either n or a smaller number that divides n. The multiplication will be equal to n if and only if the variable m is equal to 1. Notice that if m is greater than 1 it means that there is no 3 digit number whose digit multiplication is equal to n (every such number has more than 3 digits).

Finally, if m is 1 then we can just return the number which is constructed from the digits in the mul stack. Another thing to note is that the case for 0 should be handled separately (return 100).

Complexity: Because we push 3 elements at most to the stack and then stop, the run-time complexity is O(1) worst case. Space complexity is O(1) as well.

``````private static int power(int base, int n){
if (n<=0){return 1;}
int res = base;
for (int i=1;i<n;i++){res*=base;}

return res;
}

public static int findSmallestNumber(int n, int digits){
if (n<0){throw new IllegalArgumentException("n cannot be negative");}
if (digits<1){throw new IllegalArgumentException("digits must be positive");}
if (n==0){return power(10,digits-1);}

Stack<Integer> mul = new Stack<Integer>();
int m = n;
for (int i=9;(i>=1) && (mul.size()<digits);i--){
while ((m % i == 0) && (mul.size()<digits)){
mul.push(i);
m /= i;
}
}

int res = 0;
while (!mul.isEmpty()){res = 10*res + mul.pop();}

return (m>1) ? -1 : res;
}``````

In the code above digits specifies the number of desired digits in the result (for the original problem: digits = 3).

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

``````import sys

def get_product_of_digits(i):
product = 1
while(i > 0):
tmp = i%10
product = product*tmp
i=i/10
return product

def get_min_3_digit(givenN):
for i in range(100,1000):
if get_product_of_digits(i) == givenN:
return i;
return -1

def main():
givenN = int(sys.argv[1])
if givenN < 0:
print("given < 0")
else:
print get_min_3_digit(givenN)

if __name__ == '__main__':
main()``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

``````public static void findThreeDigitNumber(int num)
{
int r=0;
if(num>=1)
{
for(int i=1;i<10;i++)
{
if(num % i==0)
{
int temp=num/i;
for(int j=1;j<10;j++)
{
if(temp%j==0 && temp/j<10)
{
r=(temp/j)*100+(j)*10+num/temp;
}
}
}
}}
System.out.println(r);
}``````

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.