Find the minimum number of ingredients to be used

Input : Given T test cases.

For each test cases, k is given. k is the number of ingredients.

Following k, there are k lines. Each line has 3 numbers. They represent protein, fat and carbohydrate content in the kth ingredient.

Following these k lines, 3 lines are given. Each line has 3 numbers. They represent protein, fat and carbohydrate. For these 3 targets, we need to find out the ingredients to be added to exactly match the target.

Output : for the 3 lines in each test case, print space separated numbers denoting the ingredients to be added to get the exact match.
The ingredients must be printed in the sorted order. If there are many combinations, print the one which minimum number of ingredients.

Sample input/output:
1 //testcases
5 3 // 5 ingredients 3 targets
1 2 3 //1st ingredient
4 5 6 //2nd …
7 8 9
9 18 12
5 7 9 //5th ingredient
5 7 9 //1st target
11 13 15 //2nd target
52 14 3 // 3rd target

Expected output:
5
2 3
-1

Note: -1, when no combination(s) found

Here i have solved it by using Merge Sort and get all possible combinations.

https://paste.ubuntu.com/p/BFrmN3KNkc/

Is there any other way to solve this problem?

please mention the source of problem so we can know it’s not live.

2 Likes

I am trying this from geeksforgeeks!

This would be the naive solution with exponential complexity.

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

struct ingredient
{
int protein;
int fat;
int carbs;
};

int main()
{
int t;
cin>>t;
while(t–)
{
int n,target;
cin>>n>>target;
struct ingredient s1[n];
for(int i=0;i<n;i++)
{
cin>>s1[i].protein>>s1[i].fat>>s1[i].carbs;
}
//targets
int p,f,c;
for(int i=0;i<target;i++)
{
bool flag=false;
cin>>p>>f>>c;
for(int i=0;i<n;i++)
{
if((p==s1[i].protein) && (f==s1[i].fat) && (c==s1[i].carbs))
{
cout<<i+1<<endl;
flag=true;
break;
}
for(int j=i+1;j<n;j++)
{
if((p==s1[i].protein+s1[j].protein) && (f==s1[i].fat+s1[j].fat) && (c==s1[i].carbs+s1[j].carbs))
{
cout<<i+1<<" β€œ<<j+1<<endl;
flag=true;
break;
}
}
}
if(flag==false)
{
cout<<”-1"<<endl;
}
}
}
return 0;
}

To optimize it sort the array using one bool comparator function(for protein only) and apply binary search(log n).

1 Like

https://paste.ubuntu.com/p/BFrmN3KNkc/

Its (2^n logn) :expressionless:

for _ in range(int(input())):
ing = []
n,t = map(int,input().split())
for i in range(n):
ing.append(list(map(int,input().split())))

for _ in range(t):
    ans = []
    val = list(map(int,input().split()))
    for i in range(n):
        for j in range(i,n):
            lst = ing[i:j+1]
            temp = [0,0,0]
            for i in range(len(lst)):
                temp[0] += lst[i][0]
                temp[1] += lst[i][1]
                temp[2] += lst[i][2]
                
            if temp == val:
                ans.append(lst)
    if not ans:
        print(-1)
        break
    minlen = ans[0]
    for an in ans:
        if len(minlen) > len(an):
            minlen = an
    for val in minlen:
        print(ing.index(val)+1,end=" ")
    print()
1 Like