Amazon Interview Question
SDE1sCountry: India
Interview Type: In-Person
Min could be guaranteed, i is in the increasing order and will be returned once i equals to the given N.
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()
#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;
}
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?
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);
}
/* 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));
}
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));
}
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.
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));
}
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;
}
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);
}
}}}
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}
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;
}
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]);
}
}
}
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--;
}
}
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.
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)
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;
}
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.
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();
}
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.
#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;
}
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);
}
}
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);
}
}
// 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;
}
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));
}
}
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));
}
}
{
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));
}
}
}
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).
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()
- praveenkcs28 February 14, 2014