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

- praveenkcs28 February 14, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

How to guarantee you get smallest 3 digits number?

- Anonymous February 14, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous February 14, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@praveenkcs28: what is the logic here?

- aka February 15, 2014 | Flag
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()

- Ehsan February 15, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- anonymous February 15, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Ehsan February 15, 2014 | Flag
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;

}

- wy250801860 February 14, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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?

- Anonymous February 17, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous February 17, 2014 | Flag
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);
	}

- yugandharr147 February 14, 2014 | Flag Reply
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.

- Muhammad Adel February 14, 2014 | Flag
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));
}

- sekhar pedamallu February 14, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- sekhar pedamallu February 14, 2014 | Flag
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.

- aka February 14, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Graveton February 14, 2014 | Flag
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));
}

- sekhar pedamallu February 14, 2014 | Flag Reply
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;
}

- MuhammadAdel February 14, 2014 | Flag Reply
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);
}
}}}

- Abhishek Kumar February 14, 2014 | Flag Reply
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}

- glk February 14, 2014 | Flag Reply
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}

- glk February 14, 2014 | Flag Reply
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).

- Anonymous February 14, 2014 | Flag
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;
}

- Westlake February 14, 2014 | Flag Reply
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]);
		}
	}
}

- RiponCoder February 14, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

@RiponCoder: would it work for 8?

- aka February 15, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- RiponCoder February 15, 2014 | Flag
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--;
	}
}

- Anonymous February 14, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

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

- Ofer Skulsky February 14, 2014 | Flag Reply
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)

- pain February 15, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

if N=120 then?

- Muthu February 18, 2014 | Flag
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)

- pain February 15, 2014 | Flag Reply
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;
}

- Anonymous February 15, 2014 | Flag Reply
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.

- Learner February 15, 2014 | Flag Reply
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;
result.add(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();
}

- Vasile Dirla February 15, 2014 | Flag Reply
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.

- RI February 15, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

if N=120 then?

- Muthu February 18, 2014 | Flag
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;
}

- Kyle Shamblin February 16, 2014 | Flag Reply
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);



}
}

- chandan pradhan February 16, 2014 | Flag Reply
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);
    
        
    
     }
}

- chandan pradhan February 16, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- chandan pradhan February 16, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Test for 99 ,999, 720

- Vikash February 16, 2014 | Flag
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))))

- Jonathan February 16, 2014 | Flag Reply
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;
}

- Weining February 18, 2014 | Flag Reply
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;
}

- Lakshmi Narayana February 18, 2014 | Flag Reply
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)
a.add(i);

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

}

}

- simplyankush February 19, 2014 | Flag Reply
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)
a.add(i);

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

}

}

- simplyankush February 19, 2014 | Flag Reply
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)
a.add(i);

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

}

}
}

- simplyankush February 19, 2014 | Flag Reply
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).

- IvgenyNovo February 19, 2014 | Flag Reply
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()

- Summer February 27, 2014 | Flag Reply
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);
	}

- yugandharr147 February 14, 2014 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More