Recipe beginner problem

editorial
, , , ,
1

https://www.codechef.com/viewsolution/15442417
when i tested all limits it worked fine, codechef showed it gives wrong answer. probably am missing any bound, can anyone help me?

2

NumberOfIngredientsDevisible=0;
for(int i=0;i<NumberOfIngredients;i++){
if(ingredients[i]%min==0){
NumberOfIngredientsDevisible++;
}

This logic fails for cases like-

4 10 12 14 16

Here the reduced form is 5 6 7 8 but none of numbers are divisible by min. What you should do is, check if each number is divisible by 2, if yes, keep dividing by 2 till they are not divisible by 2 any more. then check for 3 and so on.

OR

Try using prime factorisation. Storing the prime factors will let you reduce them to lowest terms easily. You only need factors and their count which are common to all elements.

1 Like
3

You are making the code bit complicated than necessary. To reduced to minimum possible recipe items, all you need to do is find gcd (because you can divide each item only by the number of times it is common to each item, which in other words implying to the gcd value. Any other number would give you a fraction item) and then divide each item by gcd.

Below is my quick code:

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

int main(){
	int t;
	cin>>t;
	
	while(t--){
		int n;
		cin>>n;
		
		int a[n], d = 0;
		
		for(int i=0;i<n;i++){
			cin>>a[i];
			d = __gcd(d,a[i]);
		}
		for(int i=0;i<n;i++) cout<<a[i]/d<<" ";
		cout<<"\n";
	}
		
	return 0;
}
4

you have to find gcd of an array. complexity is the key.https://www.codechef.com/viewsolution/13799765

5

thanks for clarifying things :slight_smile:

1 Like
6

You’re welcome dear :slight_smile: