The following problem had the easiest solution but I don’t want to just copy and paste someone’s code as I’ve already coded a logic which might have some error.
The logic works with the test examples but fails when I submit it. Please review my logic and help me out.
int main(void) {
// your code goes here
int arr[N],t,n,i,sum,temp;
scanf(“%d”,&t);
while(t–)
{
scanf(“%d”,&n);
sum=0;
for(i=0;i<n;i++)
{
scanf(“%d”,&arr[i]);
sum+=arr[i];
}
temp=arr[0];
//finding GCD
while(sum!=temp)
{
if(sum > temp)
sum -= temp;
else
temp -= sum;
}
// printing…
for(i=0;i<n;i++)
{
if(arr[i]%sum==0)
{
arr[i]=arr[i]/sum;
}
printf(“%d “,arr[i]);
}
printf(”\n”);
}
return 0;
}
Some advice for future posts:
- Don’t just copy paste your code in the description. Provide a submission link ( CodeChef: Practical coding for everyone in your case ) or an ideone.com link instead.
The while
loop at line 17 calculates the \gcd of a[0] and a[0]+a[1]+a[2] \ldots a[n-1] and you output each element divided by that \gcd.
Unfortunately, that solution is not correct.
You can use \gcd(a[0], a[1], \ldots, a[n-2], a[n-1]) = \gcd( \gcd(a[0], a[1], \ldots, a[n-2]), a[n-1]) to arrive at the correct solution.
I would suggest you try to solve it by yourself before looking at the correct solution.
Thank You, I was confused, Will calculating gcd of each value with another will give different value than what gcd is calculated by me ?
That’s the confusion which made it happen.
I don’t understand what you mean by this: ( another what? )
To solve this problem you need the \gcd of the whole array which, as I mentioned before is not the same as what you calculated.
To calculate the \gcd of the whole array, you can use the following code:
g=0;
for( int i=0; i<n; ++i )
g = gcd(g,a[i]);
At the end of this loop, g will contain the required \gcd.