How can I use this code to get the \"Maximum Number not Possible?\" How and wher

Question

How can I use this code to get the "Maximum Number not Possible?"

How and where to enter my input?

For example. I want to input 4 and 7. And get the Maximum Number not Possible : 17

#include <bits/stdc++.h>
using namespace std;

bool isSumPossible(int arr[],int n,int s)
{
if(s<0||n<=0)
return false;
if(s==0)
return true;
return ((isSumPossible(arr,n,s-arr[n-1])) || (isSumPossible(arr,n-1,s)));
}

int main()
{
int* arr;
int n;
cout<<"Enter the Size of Array ";
cin>>n;
arr=new int[n];
cout<<"Enter the value in Array ";
int prod=1;
for(int i=0;i<n;i++)
{
cin>>arr[i];
prod*=arr[i];
}
  
int i=0;
  
for(i=prod;i>=1;i--)
{
if(isSumPossible(arr,n,i)==false)
{
break;
}
}
  
cout<<"Maximum Number not Possible : "<<i<<endl;
  
return 0;
}

Explanation / Answer

#include <iostream.h>
#include<conio.h>

//using namespace std;

int isSumPossible(int arr[],int n,int s)
{
   if(s<0||n<=0)
       return 0;
   if(s==0)
       return 1;
   return ((isSumPossible(arr,n,s-arr[n-1]) ));
}

//main method
int main()
{
   int* arr;
   int n,i,prod;
  
   clrscr();
   cout<<"Enter the Size of Array: ";
   cin>>n;

   //initializing the array
   arr=new int[n];

   cout<<"Enter the value in Array: ";

   prod=1;
  
   for(i=0;i<n;i++)
   {
       //here we are taking the input values
       cin>>arr[i];

       //computing the product for given array elements.
       prod*=arr[i];
   }

   i=0;
   cout<<" Product of array elements:"<<prod<<endl;

   for(i=prod;i>=1;i--)
   {
       //here we are taking only the first half. since it readucing the number of recursions.
       if(isSumPossible(arr,n,i)==0)
       {
           break;
       }
   }

   cout<<"Maximum Number not Possible : "<<i<<endl;

   return 0;
}

/*
   output:
   Enter the size of Array:5
   Enter the values in Array:
   1 2 3 4 5
   Product Of arrays is 120
   Maximum Number not Possible :119
*/

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.