CareerCup

C++ recursive version.

Output:

98

Code:

#include <iostream>
#include <cmath>

long max_number_recurse(int o, long limit, long total) {
	if (o == 0)
		return total;
	
	long result = 0;
	for (int i = 2; i <= 9; i++) {
		long maxn = max_number_recurse(o-1, limit, total * i);
		if (maxn > result && maxn <= limit)
			result = maxn;
	}
	
	return result;
}

long max_number(int n, int o) {
	if (n <= 0 || o <= 0)
		return -1;
		
	long limit = std::pow(10, n) - 1;
	return max_number_recurse(o, limit, 1);
}

int main() {
	std::cout << max_number(2, 3) << std::endl;
	return 0;
}

int find_max_number_recursive(int current, int rest_numbers, const int max_value, int last)
{
  if (rest_numbers == 0)
    return current;

  int result = current;
  for (int i = last; i < 10; ++i)
    if (current * i <= max_value)
    {
      result = max(result, find_max_number_recursive(current * i, rest_numbers - 1, max_value, i));
    }

  return result;
}

int find_max_number(int max_number_of_multiplications, int max_result_length)
{
  if (max_result_length < 2 || max_number_of_multiplications < 2)
    return -1;
  if (max_result_length > 8 || max_number_of_multiplications > 30)
    return -1;

  int max_value = (int)(pow(10, max_result_length) - 1);
  return find_max_number_recursive(1, max_number_of_multiplications + 1, max_value, 2);
}


int main()
{
  double t = clock();
  cout << find_max_number(30, 8) << endl;
  cout << (clock() - t) / CLOCKS_PER_SEC;
  return 0;
}

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