Amazon Interview Question
Software Development ManagersCountry: India
Good solution.
I think it's possible to use a Stack instead of a priority queue because the numbers are added in a non increasing order, hence there's no point for the data structure itself to maintain the order of its elements.
public static int getK(int n){
if (n<1){return -1;}
if (n==1){return 1;}
Stack<Integer> factors = new Stack<Integer>();
int rem = n;
for (int d=9;d>=2;d--){
while (rem % d == 0){
factors.push(d);
rem/=d;
}
}
int k = 0;
while (!factors.isEmpty()){k = 10*k + factors.pop();}
return (rem==1) ? k : (-1);
}
// divide the number from 9 to 2
// if given number is divided by more then once from one digit then divide
record all the divider
and then sort the divider in ascending order
bool findAllDivident( int p_number, vector<int> &p_divident ){
int l_startDivide = 9;
int l_index=0;
for(; l_startDivide >= 2 && p_number != 1; ){
if( (p_number % l_startDivide ) == 0 ){
p_divident.push_back( l_startDivide ) ;
p_number /= l_startDivide;
}
else
l_startDivide--;
}
return p_number == 1? true : false;
}
//after that sort the vector we will get lowest number
public static int productOfDigitsEqualToNumber(int inputNumber) {
if (0 <= inputNumber && inputNumber <= 9) {
return inputNumber;
}
if (inputNumber < 0) {
inputNumber = Math.abs(inputNumber);
}
int smallestNumber = 0;
int factor = 1;
while (inputNumber > 1) {
for (int i = 9; i > 1; i--) {
if (inputNumber % i == 0) {
inputNumber = inputNumber / i;
smallestNumber = smallestNumber + i * factor;
factor = factor * 10;
if (inputNumber == 1) {
return smallestNumber;
}
break;
} else if (i == 2) {
return -1;
}
}
}
return -1;
}
1. To be the smallest number, all the digits have to be in ascending order.
2. To get those digits, keep dividing N with numbers from 2 thru 9 (Lets say this is "i" in a for loop of 2 thru 9).
3. If N is divisible by i, divide and store the result of the division back in N. Keep this "i" as left most digit of the result. If N is still divisible, repeat this step without incrementing the for loop counter (i).
4. One more last point, to get the lowest number run the loop in reverse, i.e. from 9 thru 2.
5. Finally after all divisions done, we should get N = 1 for a success use case. Else make the result as -1.
6. Break from the loop if you get N = 1.
Sample Input: 100
N = 100
Start i = 9 (100 is not divisible by 9). Keep decrementing i by 1.
Hence i = 8, 7, 6, 5 (100 is divisible by 5)
N = N / i. thats N = 100/5 = 20. Keep i as the leftmost digit of the result. result = 5.
N is still divisible by 5.
N = N / i. thats N = 20/5 = 4. Keep i as the leftmost digit of the result. result = 55.
Now N is no more divisible by 5.
Decrement i by 1. i = 4 (4 is divisible by 4)
N = N / i. thats N = 4/4 = 1. Keep i as the leftmost digit of the result. result = 455.
Now N = 1, Exit.
Result = 455
Sample Input: 16
N = 16
Start i = 9 (16 is not divisible by 9)
Decrement i by 1. i = 8 (16 is divisible by 8)
N = N / i. thats N = 16/8 = 2. Keep i as the leftmost digit of the result. result = 8.
Decrement i by 1. i = 7 (100 is not divisible by 7). Keep decrementing i by 1.
Hence i = 6, 5, 4, 3, 2 (2 is divisible by 2)
N = N / i. thats N = 2/2 = 1. Keep i as the leftmost digit of the result. result = 28.
Now N = 1, Exit.
Result = 28
Here is the java code...
public static void main(String[] args) {
int number = 100;
int result = 0;
int count = 1;
for (int i = 9; i > 1; i--) {
while (0 == number % i) {
result = i * count + result;
number /= i;
count *= 10;
}
if (1 == number) break;
}
if (1 != number) result = -1;
System.out.println(result);
}
// divide the number from 9 to 2
// if given number is divided by more then once from one digit then divide
record all the divider
and then sort the divider in ascending order
bool findAllDivident( int p_number, vector<int> &p_divident ){
int l_startDivide = 9;
int l_index=0;
for(; l_startDivide >= 2 && p_number != 1; ){
if( (p_number % l_startDivide ) == 0 ){
p_divident.push_back( l_startDivide ) ;
p_number /= l_startDivide;
}
else
l_startDivide--;
}
return p_number == 1? true : false;
}
//after that sort the vector we will get lowest number
I think the below solution will do.
[1] Find the largest single digit divisor of given number, this digit will form the rightmost digit of K
[2] Next repeat [1] to find the next largest single digit divisor of the quotient of [1] which is less than or equal to digit found in [1]. The digit so found is the immediate left digit of K
[3] If no digit could be found and quotient is > 9 return -1
Examples:
N K Quotient
-----------------------------------
40 8 5
58 1
K=58
N K Quotient
-----------------------------------
26 2 13
As Quotient is > 13, so K =-1
N K Quotient
-----------------------------------
12 6 2
26 1
K=26
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--;
}
}
Yet another solution:
}}}
public static int calculateSmallestK(int N) {
int K = -1;
int buf = N;
int order = 1;
while ( buf > 9) {
if(isPrime(buf)) return -1;
for (int i = 9; i >= 2; i--) {
if (buf % i == 0) {
if (K==-1) K=0;
buf = buf / i;
K += i * order;
order *= 10;
i=9;
}
}
}
return K;
}
static boolean isPrime(int n) {
for(int i=2;i<n;i++) {
if(n%i==0)
return false;
}
return true;
}
}}}
Yet another solution in plain java:
public static int calculateSmallestK(int N) {
int K = -1;
int buf = N;
int order = 1;
while ( buf > 9) {
if(isPrime(buf)) return -1;
for (int i = 9; i >= 2; i--) {
if (buf % i == 0) {
if (K==-1) K=0;
buf = buf / i;
K += i * order;
order *= 10;
i=9;
}
}
}
return K;
}
static boolean isPrime(int n) {
for(int i=2;i<n;i++) {
if(n%i==0)
return false;
}
return true;
}
Using recursion:
#include <iostream>
using namespace std;
int append( int num, int digit )
{
return 10*num + digit;
}
int calc( int val, int result = 0 )
{
if( val < 10 ) return val;
for( int i = 9; i > 1; i-- )
{
if( val % i == 0 )
{
int sub = calc( val / i, result );
if( sub > 0 )
return append(sub, i);
}
}
return -1;
}
main()
{
int num;
cout << "Number: ";
cin >> num;
cout << calc(num) << endl;
}
public static void main(String[] args) {
int num = 20;
String numbers = "";
while (num != 1) {
for (int i = 9; i <= 9 && i != 0; i--) {
if (num % i == 0) {
numbers += "" + i;
num = num / i;
i = 9;
break;
}
}
}
int result=0;
int givenNum = Integer.parseInt(numbers);
while(givenNum!=0) {
result = result *10 + givenNum%10;
givenNum/=10;
}
System.out.println(result);
}
The people saying to brute force divide by 2 - 9 are missing the elegance of this problem (thus showing the interviewer that they tend to brute force things).
A number is always either prime or composite. If it is composite then it can be broken into a product of primes. Prime decomposition is unique. The prime decomposition of 26 is 13 and 2. Since 13 is not a single digit number, 26 cannot be expressed as several 1 digit numbers multiplied together. Hence why in the example the problem returns k=-1.
If a given N does have a solution it will be of the form (2^a)(3^b)(5^c)(7^d)
Check for divisibility by 2,3,5 and 7 using the modulo operation. Use this to find the values of a,b,c and d.
while a>=3, subtract 3 from a and add an 8 to the end of your number
while a>=1 and b>=1, subtract 1 from a and 1 from b and add a 6 between 5 and 7
while a>=2, subtract 2 from a and add a 4 between 3 and 5.
while b>=2, subtract 2 from b and add a 9 to the end of your number.
expand all your numbers out (eg 2^a becomes 22222....a times).
And that's it.
1) Divide number in multiple of 2,3,5,7 of number. For given number: 2 * 2 * 5 *5
2) Backward, keep on multiplying adjacent number as long as multiple is a single digit (< 10) and create new digit and put new digit in place of that number. for given number: 4 * 5* 5
3) repeat step 2, u wont have to do it much.concatenate digits in sorted order. Result it: 455
4) if number can not be divided into multiple of 2, 3, 5, 7 only, then return -1
Example: 40 => 2 * 2 * 2 * 5 = 8 * 5 = 5 * 8 = 40
Example: 1260 => 2 * 2 * 3 * 3 * 5 * 7 = 4 * 9 * 5 * 7 = 4 * 5 * 7 * 9 = 4579
Example: 12 => 2 * 2 * 3 = 2 * 6 = 26
static void Main(string[] args)
{
int sayi = Convert.ToInt32(Console.ReadLine());
//iteration number
int donmeSayisi = sayi / 2;
//list of numbers that can divide "sayi"
List<int> bolenListesi = new List<int>();
for (int i = 2; i <= donmeSayisi; i++)
{
if (sayi % i == 0)
{
bolenListesi.Add(i);
sayi = sayi / i;
i--;
}
}
//returns -1
if (bolenListesi.Any(a => a > 9) || bolenListesi.Count == 0)
{
Console.WriteLine(-1);
}
//returns number
else
{
int donme = bolenListesi.Count - 1;
for (int i = donme; i >0 ; i--)
{
if (bolenListesi[i] * bolenListesi[i - 1] < 10)
{
bolenListesi[i] = bolenListesi[i] * bolenListesi[i - 1];
bolenListesi.RemoveAt(i - 1);
}
}
//Sort it
List<int> liste = new List<int>();
for (int i = 0; i < bolenListesi.Count; i++)
{
liste.Add(0);
}
foreach (int item in bolenListesi)
{
int c = 0;
foreach (int item1 in bolenListesi)
{
if (item > item1)
{
c++;
}
}
int b = liste.Count(a => a == item);
liste[c + b] = item;
}
bolenListesi = liste;
bolenListesi.RemoveAll(a=>a<1);
Console.WriteLine(string.Join("", bolenListesi));
}
Console.ReadLine();
}
it works
How about this?
int smallestK(int N)
{
int e2 = 0; int e3 = 0; int e5 = 0; int e7 = 0;
while (N % 2 == 0) { e2++; N /= 2; } // number of factor 2
while (N % 3 == 0) { e3++; N /= 3; } // number of factor 3
while (N % 5 == 0) { e5++; N /= 5; } // number of factor 5
while (N % 7 == 0) { e7++; N /= 7; } // number of factor 7
if (N != 1)
return -1;
int a = e2 % 3;
int b = e2 / 3;
int k = 0;
if (a == 1)
k = 2;
else if (a == 2)
k = 4;
while (b-- > 0) k = k * 10 + 8;
a = e3 % 2;
b = e3 % 2;
if (a)
k = k * 10 + 3;
while (b-- > 0) k = k * 10 + 9;
while (e5-- > 0) k = k * 10 + 5;
while (e7-- > 0) k = k * 10 + 7;
return k;
}
Number should be as small as possible (e.g. 40 -> 58, not 85), easily remedied by following the procedure and adding the digit to a priority queue if the next product is >= 10.
However, the above algorithm still doesn't work for 12. The algorithm will follow 2 * 2 * 3 -> 4 * 3 -> 34, but the answer ought to be 26.
Operating on the principle of using fewest digits by combining as many small factors as possible is nice, but instead of an array of single digit primes, consider using all digits from 9 to 2:
Just poll all elements of the priority queue and concatenate, will yield smallest K.
- Booley January 27, 2014