given the sum and product of n numbers we have to find those numbers(any one
possibility)
sum, product and n are inputs...
for example if the sum is 10, product is 36 and n is 3
then 3,3,4 is a possible solution...
if it is impossible we should print NO
i wrote this code.. is there any faster ways without finding the factors?
#include<iostream>
#include<math.h>
#include<stdio.h>
using namespace std;
int requiredsum, requiredprod,n;
int chosen[1005];
bool find(int c,int sum,int prod, int arr[], int elements, int tochoose){
if(tochoose==0){
if(prod==requiredprod&&sum==requiredsum)
return 1;
else
return 0;
}
for(int i=0;i<elements;i++)
{
chosen[c]=arr[i];
if(find(c+1,sum+arr[i],prod*arr[i],arr,elements,tochoose-1))
{
for(int j=0;j<n;j++)
cout<<chosen[j]<<" ";
exit(1);
}
}
return 0;
}
int main(){
int s,p;
freopen("input6.txt","r",stdin);
//freopen("output6,txt","w",stdout);
cin>>s>>p>>n;
requiredsum=s; requiredprod=p;
int factors[1005];
int k=0;
for(int i=1;i<=sqrt(p);i++)
{
if(p%i==0)
{factors[k++]=i;
if(i*i!=p)
factors[k++]=p/i;
}
}
if(!find(0,0,1,factors,k,n))
printf("NO");
return 0;
}
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
