Help me in MINNOTES

general
1

https://www.codechef.com/viewsolution/1060685144
Why i am getting wrong ans ?
if Possible give testcase

2

@vanshwari
here plzz refer my c++ code i have implemented much similar logic
one edge case for n==1;

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

int main() {
	// your code goes here
	int t;
	cin>>t;
	while(t--)
	{
	   long long int n;
	   cin>>n;
	   long long int a[n],g,sm=0,gc,val,ans=1e15;
	   map<long long int,long long int> mp,mpb;
	   for(int i=0;i<n;i++)
	   {
	       cin>>a[i];
	       sm+=a[i];
	       if(i==0)
	       {
	           g=a[0];
	       }
	       else
	       g=__gcd(g,a[i]);
	       mp[i]=g;
	   }
	   if(n==1)
	  {
	      cout<<1<<endl;
	      continue;
	  }
	   for(int i=n-1;i>=0;i--)
	   {
	       if(i==n-1)
	       g=a[i];
	       else
	       g=__gcd(g,a[i]);
	       mpb[i]=g;
	   }
	   for(int i=0;i<n;i++)
	   {
	       if(i==0)
	       {
	           gc=mpb[i+1];
	           val=(sm-a[i])/gc;
	           ans=min(ans,val+1);
	       }
	       else if(i==n-1)
	       {
	           gc=mp[n-2];
	           val=(sm-a[i])/gc;
	           ans=min(ans,val+1);
	       }
	       else
	       {
	           gc=__gcd(mpb[i+1],mp[i-1]);
	           val=(sm-a[i])/gc;
	           ans=min(ans,val+1);
	       }
	       //cout<<val<<endl;
	       //cout<<gc<<endl;
	       //cout<<ans<<endl;
	   }
	   cout<<ans<<endl;
	}
	return 0;
}
1 Like
3

no i have run my code for n==1
and its working fine for n==1 its giving output 1

4

i found a mistake in my code but still getting wrong ans
ans=max(ans,pre[n-1]);
ans=max(ans,pre[n-2]);

5

@vanshwari
just go through my code once u will get the intuition .
also use all variable as long long int to avoid integer overflow issue.

6

i got where the ans is wrong
my approach will fail on testcase like this 1 2 16
here finding max will not give correct answer

7

remove Ai and find min, try prefix arrays