## Microsoft Interview Question

Software Engineers**Country:**United States

I just tested this. This works perfectly. Other solutions are giving 94 and 98 as answers. This solution correctly gets you 49 and 89.

```
static int smallestFactors(int n)
{
if (n < 10)
{
return n;
}
List<int> list = new List<int>();
for (int i = 9; i > 1; i--)
{
while ((n % i) == 0)
{
n /= i;
list.Add(i);
}
}
if (n > 10)
{
return 0;
}
int result = 0;
list.Reverse();
foreach (var i in list)
{
result = result * 10 + i;
}
return result;
}
```

This is the correct solution (in C#)

```
static int smallestFactors(int n)
{
if (n < 10)
{
return n;
}
List<int> list = new List<int>();
for (int i = 9; i > 1; i--)
{
while ((n % i) == 0)
{
n /= i;
list.Add(i);
}
}
if (n > 10)
{
return 0;
}
int result = 0;
list.Reverse();
foreach (var i in list)
{
result = result * 10 + i;
}
return result;
```

}

This is the correct solution in Python 3

```
def smallestFactors(n):
list = []
if n < 10:
return n
for i in range(9, 1, -1):
while 0 == n % i:
n = n / i
list.append(i)
if n > 10:
return 0
result = 0
for i in reversed(list):
result = result * 10 + i;
return result
value = smallestFactors(36)
print("the answer is ", value);
value = smallestFactors(72)
print("the answer is ", value);
```

```
unction smallest_factors(n) {
let result = `no result found for ${n}`,
product;
if( n < 10 ) return n;
for(let i=+n+1; i<Number.MAX_SAFE_INTEGER; i++) {
const sa = (''+i).split('');
//console.log(sa);
product = sa.reduce((acc,cur) => {
//console.log(`entered reduce: acc=${acc}, cur=${cur}`);
acc *= +cur;
//console.log(`leaving reduce: acc=${acc}, cur=${cur}`);
return acc;
}, 1);
//console.log(`product=${product}`);
if( n == product ) {
result = i;
break;
}
}
return result;
}
```

```
unction smallest_factors(n) {
let result = `no result found for ${n}`,
product;
if( n < 10 ) return n;
for(let i=+n+1; i<Number.MAX_SAFE_INTEGER; i++) {
const sa = (''+i).split('');
product = sa.reduce((acc,cur) => {
acc *= +cur;
return acc;
}, 1);
if( n == product ) {
result = i;
break;
}
}
return result;
}
```

```
import java.util.*;
import java.lang.*;
import java.io.*;
class test
{
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
Scanner s=new Scanner(System.in);
int n=s.nextInt();
for(int i=n+1;i<2*n;i++){
int result=1;
int t=i;
while(t>0){
result=result*(t%10);
t=t/10;
}
if(result==n){
System.out.println(i);
break;}
}
}
}
```

if numbers are prime it will not print any thing.

Divide the number recursively with the largest digit possible (9,8,...,2). Save the digit at each step.

```
int reverse(int& value)
{
int reverseNum = 0;
while(value)
{
int digit = value % 10;
reverseNum = reverseNum*10 + digit;
value = value/10;
}
return reverseNum;
}
int main(int argc, const char * argv[]) {
int number=27, answer = 0;
int i=9;
while(i > 1)
{
while(number%i == 0)
{
answer = answer*10 + i;
number = number/i;
}
i--;
}
if(number > 1)
cout<<"Not feasible";
else
cout<<reverse(answer); //reverse the digits
return 0;
}
```

Looking for interview experience sharing and coaching?

Visit AONECODE.COM for ONE-ON-ONE private lessons by FB, Google and Uber engineers!

SYSTEM DESIGN

ALGORITHMS (conquer DP, Greedy, Graph, Advanced Algorithms, Clean Coding),

latest interview questions sorted by companies,

mock interviews.

Get hired from G, U, FB, Amazon, LinkedIn, Yahoo and other top-tier companies after weeks of training.

Email us aonecoding@gmail.com with any questions. Thanks!

SOLUTION:

followup: what if we need to worry about the integer overflow?

- aonecoding June 06, 2018