CareerCup

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

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;

}

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

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}

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)

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

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

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

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()

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