Directi Interview Question
Country: United States
Aligned better for careercup:
uint cutoff, max; //cutoff: upperbound for valid product (e.g., 1000 if N=3)
void _func(uint O, uint prod, uint prev)
{
if(O==0) {
if(cutoff/10<=prod && prod<cutoff && prod>max) max=prod; return;
}
for(int i=9; i>=prev; i--) _func(O-1, prod*i, i);
}
uint func(uint N, uint O)
{
for(cutoff=1; N>;0; cutoff *=10, N--) ;
max=-1, _func(O, 1, 2); //last "2" controls min. digit
return max;
}
Here is the implementation in java ....
I am using reverse approach. Diving the given numbers (in digits) and adding all divisors in result set..if we have more or less divisors than it is a failures.
public static List<Integer> findFactors(int N, int O){
int x = 1;
int tmp = 1;
for(int i = 1; i <= N; i++){
x = x*10;
tmp = tmp*2;
}
x = x-1;
//System.out.println("This is the number: " + x);
for(int i = x; x >= tmp; i--){
List<Integer> result = check(i, O) ;
if(result != null){
System.out.println("This is the number: " + i);
return result;
}
}
throw new RuntimeException("It does not match the requirement");
}
private static List<Integer> check(int Y, int N){
int tmp = Y;
List<Integer> factors = new ArrayList<Integer>(N);
for(int X = 2; X< 9; X++){
for(int i = 0; i< N; i++){
if(tmp%X != 0){
factors.clear();
tmp = Y;
break;
}
factors.add(X);
tmp = tmp/X;
if(tmp >= 2 && tmp <= 9){
factors.add(tmp);
if(factors.size() == 3){
return factors;
}
break;
}
}
}
//System.out.println(factors);
return null;
}
public static void main(String[] args) {
System.out.println(findFactors(2,3));
}
Sorry edit facility is not avilable so i am submitting it again .... here is with minor fix....it was not working for N=1, O = 3
public static List<Integer> findFactors(int N, int O){
int x = 1;
int tmp = 1;
for(int i = 1; i <= N; i++){
x = x*10;
tmp = tmp*2;
}
x = x-1;
//System.out.println("This is the number: " + x);
for(int i = x; x >= tmp; i--){
List<Integer> result = check(i, O) ;
if(result != null){
System.out.println("This is the number: " + i);
return result;
}
}
throw new RuntimeException("It does not match the requirement");
}
private static List<Integer> check(int Y, int N){
int tmp = Y;
List<Integer> factors = new ArrayList<Integer>(N);
for(int X = 2; X< 9; X++){
for(int i = 0; i< N; i++){
if(tmp%X != 0){
factors.clear();
tmp = Y;
break;
}
factors.add(X);
tmp = tmp/X;
if(tmp >= 2 && tmp <= 9 && factors.size() == 2){
factors.add(tmp);
return factors;
}
}
}
//System.out.println(factors);
return null;
}
public static void main(String[] args) {
System.out.println(findFactors(2,3));
}
Do you mean:
if(tmp >= 2 && tmp <= 9 && factors.size() == 2){ -> if(tmp >= 2 && tmp <= 9 && factors.size() == N-1){ as N is 3 in this case.
Awesome question! Where did you get this from?
The question is basically asking to find subsets of size O such that :
- product of subset elems is less than or equal to max number that can be formed by N digits
logic would be to first get the targetNum i.e max num that can be formed using N digits:
simple logic would be
int x= N
while(x) {
res = res*10+9;
x--;
}
return res;
Lets call the above res as "target_prod"
Once u have this, our method would be to generate all possible subsets of length<=O and in our recrusion, if our subset length>O (O not zero) or if our prodct > target_prod, we return. If it is equal to O, we compute the product and update our current result accordingly.
This is a modification of the knapsack problem (check wiki). The maximum weight the knapsack can hold is the number of operations. The weights are assigned to be one (as they take one operation) and the values are the numbers itself (2 to 9). There is an additional constraint to the maximum value('limit' variable in my program, limit=10^N-1) , which is decided by the number of digits the calculator can display. I had written a program for the knapsack problem earlier, which I have modified to suit this problem. Another subtle difference is that the value (2 to 9) is multiplied to the max value instead of being added as in the case of the knapsack problem. The program is quite fast for a variety of inputs. Additional checks can be added to optimize the program, as when the O<=N (number of operations<= number of digits), then the output should always be 9^O, and there is no need to call the recursive function at all!(verify), which I have not implemented. Hope this solution helps. Enjoy!
#include<iostream>
using namespace std;
int directi(int w,int itemw[], int itemv[],int noi,int limit)
{
int temp=1,temp1=1;
for(int i=0;i<noi;i++)
{
if(w>=itemw[i])
{
temp1=directi(w-itemw[i],itemw,itemv,noi,limit/itemv[i]);
if(temp1*itemv[i]>temp&& temp1*itemv[i]<=limit)
temp=temp1*itemv[i];
}
}
return temp;
}
int main()
{
int itemw[10];int itemv[10];
int w; int noi;int limit;
cout<<"enter the max no of operations: ";//cout<<"enter the knapsack capacity: ";
cin>>w;
//cout<<"enter the no of items: ";
noi=8;//cin>>noi;
cout<<"enter the limit: ";
cin>>limit;
for(int i=0;i<noi;i++)
{
//cout<<"\nenter item weight: ";
itemw[i]=1;//cin>>itemw[i];
//cout<<"\nenter item value: ";
itemv[i]=i+2;//cin>>itemv[i];
}
cout<<"The maximum value is: "<<directi(w,itemw,itemv,noi,limit)<<"\n";
system("pause");
return 0;
}
dp it is!!!!
#include<iostream>
#include<vector>
using namespace std;
int maxNum(int n,int o)
{
int max=1;
for(int i=0;i<n;i++)
{
max*=10;
}
max-=1;
bool dpIS[o+1][max+1];
for(int i=0;i<=max;i++)
{
for(int j=0;j<=o;j++)
{
dpIS[j][i]=false;
}
}
for(int i=1;i<10;i++){
dpIS[1][i]=true;
}
for(int i=1;i<=max;i++)
{
for(int j=2;j<=o;j++)
{
for(int k=2;k<=9;k++)
{
if(i%k==0 && dpIS[j-1][i/k])
{
dpIS[j][i]=true;
}
}
}
}
for(int i=max;i>0;i--)
{
if(dpIS[o][i]==true)return i;
}
}
int main()
{
int n,o;
cin>>n>>o;
cout<<maxNum(n,o)<<endl;
return 0;
}
n=int(raw_input())
o=int(raw_input())
dp=[[False for x in range(0,10**n)] for x in range(0,o+1)]
dp[1][1:10]=[True for x in range(1,10)]
a=[[[]for x in range(0,10**n)] for x in range(0,o+1)]
a[1][1:10]=[[x] for x in range(1,10)]
m=1;
for i in range(2,o+1):
for j in range(1,10**n):
for k in range(2,10):
if not dp[i][j] and j%k==0 and dp[i-1][j/k]:
dp[i][j]=True;
for e in a[i-1][j/k]:
a[i][j].append(e)
a[i][j].append(k)
m=max(j,m);
print m
print a[o][m]
#include<iostream>
using namespace std;
bool largest(int num,int j,int o)
{
if(o==0&&num==1)
return true;
if(o==0||num==1)
return false;
for(int i=j;i<=9;i++)
{
if(!(num%i))
{
o--;
if(largest(num/i,i,o))
return true;
}
}
return false;
}
int main()
{
int n,o;
cin>>n>>o;
long long int num=0,num1=1;
for(int i=0;i<n;i++)
{
num=num*10+9;
}
for(int i=1;i<n;i++)
{
num1=num1*10+0;
}
bool flag=0;
for(long long int i=num;i>=num1;i--)
{
if(largest(i,2,o))
{
flag=1;
cout<<i;
break;
}
}
if(!flag)
cout<<-1;
return 0;
}
1) Generate the biggest possible number for 'n' eg. for n = 2 => 99, n=3 => 999...
2) Starting from that number check if 'o' factors exist which multiplied by each other are equal the biggestNumber.
a) If not decrements number and repeat point 2
Code:
package directi;
import java.util.ArrayList;
import java.util.List;
public class FindBiggestNumberForOMultiplications {
public static void main(String[] args) {
int n = 5;
int o = 5;
List<Integer> factors = new ArrayList<Integer>();
System.out.println(checkNum(generateBiggestNum(n), o, factors));
System.out.println(factors);
}
private static int generateBiggestNum(int n) {
int num = 9;
for (int i = 0; i < n - 1; i++) {
num *= 10;
num += 9;
}
return num;
}
private static int checkNum(int startNum, int o, List<Integer> factors) {
int num = 0;
for (num = startNum; num >= 2 * o; num--) {
if (findMultiplications(num, o, 0, 0, factors)) {
return num;
}
}
return -1;
}
private static boolean findMultiplications(int num, int o, int noOfFactors, int prevFactor, List<Integer> factors) {
if (noOfFactors > o) {
return false;
}
for (int i = 2; i <= 9; i++) {
if (num % i != 0 || i < prevFactor) {
continue;
}
noOfFactors++;
if (noOfFactors == o) {
factors.add(num);
return true;
}
if (findMultiplications(num / i, o, noOfFactors, i, factors)) {
factors.add(i);
return true;
}
}
return false;
}
}
Let uint be some unsigned integer (or plain integer in Java).
Backtrack but without repeating ways of creating same product (redundant).
e.g. 2*3 same as 3*2. So create products in increasing order only...
- Urik's twin Cookie Monster (dead now) October 31, 2013uint cutoff, max; //cutoff is upperbound for valid product (e.g., 1000 if N=3) void _func(uint O, uint prod, uint prev) { if(O==0) { if(cutoff/10<=prod && prod<cutoff && prod>max) max=prod; return; } for(int i=9; i>=prev; i--) _func(O-1, prod*i, i); //try digits greater than previous } uint func(uint N, uint O) { for(cutoff=1; N>0; cutoff *=10, N--) ; max=-1, _func(O, 1, 2); //last "2" controls min. digit return max; }