MINNOTES - Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Practice

Setter: Daanish Mahajan and Akash Bhalotia
Tester: Aryan
Editorialist: Taranpreet Singh

DIFFICULTY

Easy

PREREQUISITES

Prefix/Suffix Sum Arrays

PROBLEM

Given an array A containing N positive integers, representing salaries of N employees. You are allowed to change at most 1 integer to any value. After changing, you need to choose a denomination x such that all the employees can be paid with notes of denomination x and the number of notes used is the minimum possible.

Find the minimum number of notes used with optimal choice of changing integer, and optimal choice of denomination.

QUICK EXPLANATION

  • For a fixed array A, choosing the denomination to be the gcd of all elements of A is optimal.
  • So, we need to consider changing each element, and for each element, choosing the denomination to be the gcd of all remaining elements is the optimal choice. That way, we determine the number of nodes required if the i-th element is changed.
  • The computation of gcd of all except 1 element can be computed quickly by computing prefix gcd and suffix gcd.

EXPLANATION

Array with No updates

Let’s consider a simpler problem where you are not allowed to change the array at all. You just can choose the denomination value and you need to determine the minimum number of notes.

For denomination value x, the number of notes required are \displaystyle \sum_{i = 1}^N \frac{A_i}{x} = \frac{\sum_{i = 1}^N A_i}{x}.
So, we need

  • All A_i to be divisible by x
  • x should be the maximum possible.

So we need x to be the largest number dividing all A_i, which is satisfied by gcd of all elements of A. So we choose x = gcd(A_i) and compute minimum number of notes as \displaystyle\frac{\sum_{i = 1}^N A_i}{x}

Solving original problem slowly

So, we know how to solve it if no changes are to be made. Now, we are allowed to change one element. Let’s say we decide that i-th element must be changed, and the denomination x is chosen. It is in our best interest to change i-th element to x so that the number of notes required increases by 1 only.

Hence, let’s iterate over all elements, and assume the current element is the one that is changed, compute GCD of all other elements, and compute the minimum number of notes required, and take minimum for all chosen elements.

The following code represents the above idea in practice.

Code
ans = INF
for i in range(0, N):
    gcd, sum = 0, 0
    for j in range (0, N): 
        if i != j:
            gcd = gcd(gcd, A[i])
            sum += A[i]
    ans = min(ans, 1+(sum/gcd))

As the above code has time complexity O(N^2*log(max(A_i))), this shall TLE

Optimizing above solution

Let us try to remove the inner loop to compute sum and gcd excluding i-th element. We can see that the required gcd is GCD(A_1, A_2 \ldots A_{i-1}, A_{i+1} \ldots A_N). We can write it as GCD(GCD(A_1, A_2 \ldots A_{i-1}), GCD(A_{i+1} \ldots A_N)). The inner two terms are GCD of prefix up to A_{i-1}, and suffix starting from A_{i+1}

Let’s compute prefix GCD array and suffix GCD array for the given A.
Specifically, compute P_i = GCD(P_{i-1}, A_i) P_0 = 0 and S_i = GCD(S_{i+1}, A_i), S_{N+1} = 0. Both of these can be done in time O(N*log(max(A_i))).

Now, we can see that GCD(A_1, A_2 \ldots A_{i-1}) = P_{i-1} and GCD(A_{i+1} \ldots A_N) = S_{i+1}. So, the GCD of all elements except i is GCD(P_{i-1}, S_{i+1}). Computing sum excluding i-th element is trivial.

Edge Case

Handle N = 1 separately, as for i = 1, both P_0 = S_2 = 0, so GCD(P_0, S_2) evaluates to zero, leading to divide by zero. Since there’s only one element, we can choose denomination same as A_1, requiring only one note.

TIME COMPLEXITY

The time complexity is O(N*log(max(A_i))) per test case.

SOLUTIONS

Setter's Solution
#include<bits/stdc++.h>
# define pb push_back 
#define pii pair<int, int>
#define mp make_pair
# define ll long long int

using namespace std;
  
const int maxt = 118369, maxn = 1e5, maxtn = 1e6, maxv = 1e9;
const string newln = "\n", space = " ";
ll a[maxn + 10];
ll dp[maxn + 10][2], sum[maxn + 10][2];
int main()
{   
    int t, n; cin >> t; int tn = 0;
    while(t--){
        cin >> n; tn += n;
        for(int i = 1; i <= n; i++)cin >> a[i];
        for(int i = 1; i <= n; i++){
            sum[i][0] = sum[i - 1][0] + a[i];
            sum[n - i + 1][1] = sum[n - i + 2][1] + a[n - i + 1];
            dp[i][0] = __gcd(dp[i - 1][0], a[i]);
            dp[n - i + 1][1] = __gcd(dp[n - i + 2][1], a[n - i + 1]);
        }
        ll ans = 1e18;
        for(int i = 1; i <= n; i++){
            ll g = __gcd(dp[i - 1][0], dp[i + 1][1]);
            ans = min(ans, (g == 0 ? 0 : (sum[i - 1][0] + sum[i + 1][1]) / g) + 1);
        }
        cout << ans << endl;
        for(int i = 0; i <= n + 2; i++){
            a[i] = 0; 
            sum[i][0] = sum[i][1] = 0; 
            dp[i][0] = dp[i][1] = 0;
        }
    }
    assert(tn <= maxtn);
} 
Tester's Solution
/* in the name of Anton */

/*
  Compete against Yourself.
  Author - Aryan (@aryanc403)
  Atcoder library - https://atcoder.github.io/ac-library/production/document_en/
*/

#ifdef ARYANC403
    #include <header.h>
#else
    #pragma GCC optimize ("Ofast")
    #pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
    //#pragma GCC optimize ("-ffloat-store")
    #include<bits/stdc++.h>
    #define dbg(args...) 42;
#endif

using namespace std;
#define fo(i,n)   for(i=0;i<(n);++i)
#define repA(i,j,n)   for(i=(j);i<=(n);++i)
#define repD(i,j,n)   for(i=(j);i>=(n);--i)
#define all(x) begin(x), end(x)
#define sz(x) ((lli)(x).size())
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define endl "\n"

typedef long long int lli;
typedef long double mytype;
typedef pair<lli,lli> ii;
typedef vector<ii> vii;
typedef vector<lli> vi;

const auto start_time = std::chrono::high_resolution_clock::now();
void aryanc403()
{
#ifdef ARYANC403
auto end_time = std::chrono::high_resolution_clock::now();
std::chrono::duration<double> diff = end_time-start_time;
    cerr<<"Time Taken : "<<diff.count()<<"\n";
#endif
}

long long readInt(long long l, long long r, char endd) {
    long long x=0;
    int cnt=0;
    int fi=-1;
    bool is_neg=false;
    while(true) {
        char g=getchar();
        if(g=='-') {
            assert(fi==-1);
            is_neg=true;
            continue;
        }
        if('0'<=g&&g<='9') {
            x*=10;
            x+=g-'0';
            if(cnt==0) {
                fi=g-'0';
            }
            cnt++;
            assert(fi!=0 || cnt==1);
            assert(fi!=0 || is_neg==false);

            assert(!(cnt>19 || ( cnt==19 && fi>1) ));
        } else if(g==endd) {
            if(is_neg) {
                x=-x;
            }
            assert(l<=x&&x<=r);
            return x;
        } else {
            assert(false);
        }
    }
}
string readString(int l, int r, char endd) {
    string ret="";
    int cnt=0;
    while(true) {
        char g=getchar();
        assert(g!=-1);
        if(g==endd) {
            break;
        }
        cnt++;
        ret+=g;
    }
    assert(l<=cnt&&cnt<=r);
    return ret;
}
long long readIntSp(long long l, long long r) {
    return readInt(l,r,' ');
}
long long readIntLn(long long l, long long r) {
    return readInt(l,r,'\n');
}
string readStringLn(int l, int r) {
    return readString(l,r,'\n');
}
string readStringSp(int l, int r) {
    return readString(l,r,' ');
}

void readEOF(){
    assert(getchar()==EOF);
}

vi readVectorInt(int n,lli l,lli r){
    vi a(n);
    for(int i=0;i<n-1;++i)
        a[i]=readIntSp(l,r);
    a[n-1]=readIntLn(l,r);
    return a;
}

const lli INF = 0xFFFFFFFFFFFFFFFL;

lli seed;
mt19937 rng(seed=chrono::steady_clock::now().time_since_epoch().count());
inline lli rnd(lli l=0,lli r=INF)
{return uniform_int_distribution<lli>(l,r)(rng);}

class CMP
{public:
bool operator()(ii a , ii b) //For min priority_queue .
{    return ! ( a.X < b.X || ( a.X==b.X && a.Y <= b.Y ));   }};

void add( map<lli,lli> &m, lli x,lli cnt=1)
{
    auto jt=m.find(x);
    if(jt==m.end())         m.insert({x,cnt});
    else                    jt->Y+=cnt;
}

void del( map<lli,lli> &m, lli x,lli cnt=1)
{
    auto jt=m.find(x);
    if(jt->Y<=cnt)            m.erase(jt);
    else                      jt->Y-=cnt;
}

bool cmp(const ii &a,const ii &b)
{
    return a.X<b.X||(a.X==b.X&&a.Y<b.Y);
}

const lli mod = 1000000007L;
// const lli maxN = 1000000007L;

    lli T,n,i,j,k,in,cnt,l,r,u,v,x,y;
    lli m;
    string s;
    vi a;
    //priority_queue < ii , vector < ii > , CMP > pq;// min priority_queue .

int main(void) {
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    // freopen("txt.in", "r", stdin);
    // freopen("txt.out", "w", stdout);
// cout<<std::fixed<<std::setprecision(35);
T=readIntLn(1,12e4);
lli sumN=0;
while(T--)
{

    n=readIntLn(1,1e5);
    sumN+=n;
    a=readVectorInt(n,1,1e9);
    if(n==1){
        cout<<1<<endl;
        continue;
    }
    lli sum=0;
    for(auto &x:a)
        sum+=x;
    vi pref(n+1),suf(n+1);
    lli ans=INF;
    for(lli i=0;i<n;++i){
        pref[i+1]=__gcd(pref[i],a[i]);
    }

    for(lli i=n-1;i>=0;--i){
        suf[i]=__gcd(suf[i+1],a[i]);
    }

    ans=min(ans,sum/pref[n]);
    fo(i,n){
        lli g=__gcd(pref[i],suf[i+1]);
        ans=min(ans,1+(sum-a[i])/g);
    }
    cout<<ans<<endl;
}
    assert(sumN<=1e6);
    aryanc403();
    readEOF();
    return 0;
}
Editorialist's Solution
import java.util.*;
import java.io.*;
class MINNOTES{
    //SOLUTION BEGIN
    void pre() throws Exception{}
    void solve(int TC) throws Exception{
        int N = ni();
        long[] A = new long[2+N], pre = new long[2+N], suf = new long[2+N];
        long sum = 0;
        for(int i = 1; i<= N; i++){
            A[i] = nl();
            sum += A[i];
        }
        if(N == 1){
            pn(1);
            return;
        }
        for(int i = 1; i<= N; i++)pre[i] = gcd(pre[i-1], A[i]);
        for(int i = N; i>= 1; i--)suf[i] = gcd(suf[i+1], A[i]);
        long ans = Long.MAX_VALUE;
        for(int i = 1; i<= N; i++){
            long gcd = gcd(pre[i-1], suf[i+1]);
            long total = sum-A[i];
            long notes = total/gcd + 1;
            ans = Math.min(ans, notes);
        }
        pn(ans);
    }
    long gcd(long a, long b){return b == 0?a:gcd(b, a%b);}
    //SOLUTION END
    void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
    static boolean multipleTC = true;
    FastReader in;PrintWriter out;
    void run() throws Exception{
        in = new FastReader();
        out = new PrintWriter(System.out);
        //Solution Credits: Taranpreet Singh
        int T = (multipleTC)?ni():1;
        pre();for(int t = 1; t<= T; t++)solve(t);
        out.flush();
        out.close();
    }
    public static void main(String[] args) throws Exception{
        new MINNOTES().run();
    }
    int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
    void p(Object o){out.print(o);}
    void pn(Object o){out.println(o);}
    void pni(Object o){out.println(o);out.flush();}
    String n()throws Exception{return in.next();}
    String nln()throws Exception{return in.nextLine();}
    int ni()throws Exception{return Integer.parseInt(in.next());}
    long nl()throws Exception{return Long.parseLong(in.next());}
    double nd()throws Exception{return Double.parseDouble(in.next());}

    class FastReader{
        BufferedReader br;
        StringTokenizer st;
        public FastReader(){
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public FastReader(String s) throws Exception{
            br = new BufferedReader(new FileReader(s));
        }

        String next() throws Exception{
            while (st == null || !st.hasMoreElements()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch (IOException  e){
                    throw new Exception(e.toString());
                }
            }
            return st.nextToken();
        }

        String nextLine() throws Exception{
            String str = "";
            try{   
                str = br.readLine();
            }catch (IOException e){
                throw new Exception(e.toString());
            }  
            return str;
        }
    }
}

Feel free to share your approach. Suggestions are welcomed as always. :slight_smile:

6 Likes

#include
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
int main() {
ll t;
cin>>t;
while(t)
{

    ll n,sum=0,max=INT_MAX,x=0;
    cin>>n;
  ll arr[n];
   for(int i=0;i<n;i++)
   {
      cin>>arr[i];
      sum+=arr[i];
   }
   if(n==1)
   {
       cout<<1<<endl;
     
   }
   else
   {
   vector<ll>prefix(n),suffix(n),h(n);
   //precompuataion of gcd
   prefix[0]=arr[0];
   for(int i=1;i<n;i++)
   {
       prefix[i]=__gcd(prefix[i-1],arr[i]);
   }
   //post computation of gcd
   suffix[n-1]=arr[n-1];
   for(int i=n-2;i>=0;i--)
   {
       suffix[i]=__gcd(suffix[i+1],arr[i]);
   }
   //iss vector m  sab element ka gcd hoga bas Ith element ko chodkar means i=0 too i=1 se lekar i=n tak ka gcd hoga  
   h[0]=suffix[1],h[n-1]=prefix[n-2];
   for(int i=1;i<n-1;i++)
   {
       h[i]=__gcd(prefix[i-1],suffix[i+1]);
   }

   for(int i=0;i<n;i++)
   {
       x=(sum-arr[i])/h[i]+1;
       if(max<x)
       {
           max=x;
       }
   }
   cout<<x<<endl;
  }
   t--;
}
return 0;

}
can any one please tell me what is wrong with this code

I solved this problem by a brute-force approach, as outlined below.

Sort the array A into ascending order, to make the subsequent algorithm more efficient, where we work from small to large.

Define a class ‘Note’ containing a possible value and the number of notes required so far. This class contains functions ReduceValue and Add

We store a sorted list of Notes, sorted by value, of the possibilities encountered so far. The smallest note is obviously the one where none of the A are excluded. When a new possibility is encountered, it is ignored if a note of the value already exists, else it is inserted into the list.

We don’t know which item to exclude from the GCD, so try each in turn.

Handle the first 2 items separately at the start: there are 3 possibilities: Exclude the first or second or neither. The result may be 1, 2 or 3 differently valued notes.

Work through the remaining items in array A. First find the GCD of the smallest note with this item. If it is smaller, insert a corresponding new Note into the list, and except for the last item keep the existing note corresponding to when this item is excluded. Then find the GCD of each subsequent note in the list with this item. If it is smaller, remove this note and if a note of this reduced value does not yet exist insert it into the list. If the GCD is unchanged, add the item to the Note.

At the end loop through all the notes and choose the one with the smallest number.

You can see this solution at Solution: 48526594 | CodeChef It passed in 0.84 seconds

3 Likes

I tried an approach similar to this but my solution didnt get accepted.I cant figure out the issue with that.Can you please look into it and tell me what’s wrong.

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

int gcd(int a,int b){
int temp;
while(b > 0) {
temp = b;
b = a % b;
a = temp;
}
return a;
}

int cmpfunc (const void * a, const void * b) {
return ( (int)a - (int)b );
}

int main(void) {
int t;
scanf("%d", &t);
while(t–){
int n, x, max, y, z;
scanf("%d",&n);
int a[n];

    for(x = 0; x < n; x++) scanf("%d",&a[x]);
    
    if(n==1)
    {
    printf("%d\n",1);
    continue;
}
    
    qsort(a, n, sizeof(int), cmpfunc);
    int c1 = 0;
	    int deno;
	    for(x=0;x<n;x++)
	    {
	        if(a[x]%a[1] == 0)
	        c1++;
	    }
	    if(c1==n)
	    {
	        deno = a[1];
	        a[n-1] = a[1];
	    }
	    else if(c1==n-1)
	    {
	        
	        for(y=0;y<n;y++)
	        {
	            if(a[y] % a[1] != 0)
	            a[y] = a[1];
	        }
	        deno = a[1];
	    }
	    else
	    {
		        c1 = 0;
		        for(x=0;x<n;x++)
		    {
		        if(a[x]%a[0] == 0)
		        c1++;
		    }
		    if(c1==n)
		    {
		        deno = a[0];
		        a[n-1] = a[0];
		    }
		    else if(c1==n-1)
		    {
		        
		        for(y=0;y<n;y++)
		        {
		            if(a[y] % a[0] != 0)
		            a[y] = a[0];
		        }
		        deno = a[0];
		    }
		    else
		    {
		        int r = a[0];
                   for(int i=1; i<n; i++) {
                      r = gcd(r, a[i]);
                   }
                a[n-1] = r;
                deno = r;
		    }
	    }
    
    long long int c = 0;
    for(x = 0; x < n; x++){
        c = c + a[x]/deno;
    }
    printf("%lld\n",c);
}
return 0;

}

1 Like

Can we have the testcases used for evaluation?

Towards the end of your code I see the code block

				int r = a[0];
				   for(int i=1; i<n; i++) {
					  r = gcd(r, a[i]);
				   }
				a[n-1] = r;
				deno = r;

but suppose N = 4 and A = { 6, 9, 13, 18 }

Your code will set ‘r’ to 1, but we want to omit the 13 and keep ‘r’ = 3.

Also, the way you have implemented function GCD, you need to ensure you call it with a >= b.

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

int gcd(int a, int b)
{
if (a == 0)
return b;
return gcd(b % a, a);
}
int findGCD(int arr[], int n)
{
int result = arr[0];
for (int i = 1; i < n; i++)
{
result = gcd(arr[i], result);

    if(result == 1)
    {
       return 1;
    }
}
return result;

}

int f(int arr[],int n){
int ans=0,g;

sort(arr,arr+n);
g=findGCD(arr,n);
arr[n-1]=g;

for(int i=0;i<n;i++)
ans=ans+arr[i]/g;

return ans;

}

int main(){
int t;
cin>>t;
while(t–){
int n;
cin>>n;
int a[n];

    for(int i=0;i<n;i++)
    cin>>a[i];

    cout<<f(a,n)<<endl;
}
return 0;

}

what is wrong with this algo ?

cout<<max<endl;

i did but does not work can you please tell me test case

Whats wrong with my code , i have covered all corner cases
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
int main()
{
int t;
cin>>t;
while(t–)
{
int n;ll sum=0;
cin>>n;
if(n==1)
{
int x;
cin>>x;
cout<<“1”;
}
else
{
int *arr=new int[n],*pre=new int[n],*suf=new int[n],*fin=new int[n];
for(int i=0;i<n;i++)
{
cin>>arr[i];
max_num=max(max_num,arr[i]);
sum+=arr[i];
}
pre[0]=arr[0];suf[n-1]=arr[n-1];
for(int i=1;i<n;i++)
pre[i]=__gcd(pre[i-1],arr[i]);
for(int i=n-2;i>=0;i–)
suf[i]=__gcd(suf[i+1],arr[i]);
fin[0]=suf[1],fin[n-1]=pre[n-2];
for(int i=1;i<n-1;i++)
fin[i]=__gcd(pre[i-1],suf[i+1]);
int ans=INT_MAX;
for(int i=0;i<n;i++)
ans=min(ans,int((sum-arr[i])/fin[i]+1));
cout<<ans;
free(arr);free(pre);free(suf);free(fin);
}
if(t)
cout<<"\n";
}
return 0;
}

Can someone help me understand why is it wrong? I included the corner cases where gcd[0]=suf[0] and gcd[n-1]=pref[n-1]. Here is the code:
Thanks.

#include <bits/stdc++.h>
#define ll long long int
using namespace std;

int gcd(int a, int b){
if(a==0) return b;
return gcd(b%a,a);
}
int main(){
int t;
cin >> t;
while(t–){
int n;
cin >> n;
ll arr[n],sum=0,x;
for(int i=0;i<n;i++){
cin >> arr[i];
sum+=arr[i];
}

    if(n==1){
        cout << 1 <<endl;
        continue;
    }

    int pref[n],suf[n];

    pref[0]=arr[0];
    for(int i=1;i<n;i++){
        pref[i]=gcd(pref[i-1],arr[i]);
    }

    suf[n-1]=arr[n-1];
    for(int i=n-2;i>=0;i--){
        suf[i]=gcd(suf[i+1],arr[i]);
    }

    int gcds[n];
    gcds[0]=suf[0];
    gcds[n-1]=pref[n-1];
    for(int i=1;i<n-1;i++){
        gcds[i]=gcd(pref[i-1],suf[i+1]);
    }


    int m=-1;
    for(int i=0;i<n;i++){
        x=(sum-arr[i])/gcds[i] + 1;
        if(m==-1){
            m=x;
            continue;
        }
        if(x<m){
            m = x;
        }
    }

    cout << m <<endl;
}
return 0;

}

Can the EDGE CASE be this:
if(N<=2)
return N;

Also, if someone can point out the mistake in my code:

import java.io.*;
import java.util.Arrays;
class CodeChef{
public static void main(String[] args)throws IOException{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
int TC=Integer.parseInt(br.readLine());
while(TC–>0){
int N=Integer.parseInt(br.readLine());
int[] arr=new int[N];
int[] fact={0,0,0};
String str=br.readLine();
String[] num=str.split(" ");
for(int i=0;i<N;i++){
arr[i]=Integer.parseInt(num[i]);
}
if(N<3){
System.out.println(N);
continue;
}
int notes=0;
Arrays.sort(arr);
int pos=N-1;
int den=1;
for(int i=2;i>=0;i–){
for(int j=0;j<N;j++){
if(arr[j]%arr[i]==0){
fact[i]++;
}
else{
pos=j;
}
}
if(fact[i]==N || fact[i]==N-1 && arr[i]!=1){
den=arr[i];
break;
}
}
arr[pos]=den;
for(int i=0;i<N;i++){
notes+=arr[i]/den;
}
System.out.println(notes);
}
}
}

Can someone help me learn why is it wrong?

#include <bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin >> t;
while (t)
{
int n;
cin>>n;
int arr[n],v1[n],v2[n],v3[n];
long long sarr=0,sum,mnn=1000000001;
for(int i=0;i<n;i++)
{
cin>>arr[i];
sarr+=arr[i];
}
if(n==1||n==2)
cout<<n;
else
{
v1[0]=arr[0];v2[n-1]=arr[n-1];
for(int i=1;i<n;i++)
{
v1[i]=__gcd(v1[i-1],arr[i]);
}
for(int i=n-2;i>=0;i–)
{
v2[i]=__gcd(v2[i+1],arr[i]);
}
v3[0]=v2[1];v3[n-1]=v1[n-2];
for(int i=1;i<n-1;i++)
{
v3[i]=__gcd(v1[i-1],v2[i+1]);
}
for(int i=0;i<n;i++)
{
sum=(sarr-arr[i]+v3[i])/v3[i];
if(sum<mnn)
mnn=sum;
}
cout<<mnn;
}
cout<<endl;
t–;

}
return 0;

}

It hurts the most when you have learnt something and even recognize where to apply but fail-
I used the same approach pls help me anyone regarding the code below, - PS - It got one subtask correct while one wrong. I must be one of the corner cases. Any help is appreciated.

//સહજ
//www.linkedin.com/in/sahaj-patel-2b0b3920b/
#define ll long long
#include < iostream>
#include < vector>
#include< algorithm>
#include< cmath>
using namespace std;
#define int long long
#define pb push_back
#define ppb pop_back
#define rep(i, a, b) for(int i=a; i<b; i++)
#define vi vector
#define endl “\n”

void solve(){
    int n; cin>>n;
    int a[n];
    int mx = 0;
    int mxind = 0;
    for(int i=0; i<n; i++){
        cin>>a[i];
        if(a[i]>mx){
            mxind = i;
            mx = a[i];
        }
    }
    int pre[n+2];
    int suf[n+2];

    pre[1] = a[0];
    for(int i=2; i<=n; i++){
        pre[i] = __gcd(pre[i-1], a[i-1]);
    }

    suf[n] = a[n-1];
    for(int i=n-1; i>=1; i--){
        suf[i] = __gcd(suf[i+1], a[i-1]);
    }
    int in;
    if(suf[2]>pre[n-1]) in = 0;
    else in = n-1;
    int res = max(suf[2], pre[n-1]); // doing first and last element explicitly check which to remove
    // other than first and last now
    vi v;
    v.pb(suf[2]);
    v.pb(pre[n-1]);
    int x;
    for(int i=2; i<=n; i++){
        x = __gcd(pre[i-1], suf[i+1]);
        res = max(x, res);
    }
    bool same = 1;
    for(int i=0; i<v.size(); i++){
        if(res==v[i]){
            same = 1;
        }
        else{
            same = 0;
            break;
        }
    }
    int ans = 0;
    if(same==1){
        a[mxind] = res;
        rep(i, 0, n){
            ans += a[i]/res;
        }
        cout<<ans<<endl;
        return;
    }

    rep(i, 0, n){
        if(a[i]<res){
            a[i] = res;
        }
        ans += a[i]/res;
    }

    cout<<ans<<endl;
    return;

    
    

    


}


int32_t main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t; cin>>t;
    while(t--){
       solve();
    }
    return 0;
}

What’s wrong with this python code for this problem,
please clarify anyone

import math

def gcd(x,y):

while(y):

x,y = y,x%y

return x

def l_gcd(list):
g = 0
for x in list:
g = math.gcd(g,x)
return g
def result(list,i):
list[i]= 0
a = l_gcd(list)
# print(list,a)
s = 1
for y in list:
s += y//a
return s

for i in range(int(input())):
n= int(input())
l1 = list(map(int,input().split()))
l3 = []
for i in range(n):
b= l1[i]
r = result(l1,i)
l1[i]=b
l3.append®
# print(l3)
print(min(l3))

@prashant_kr933 I looked at your latest attempt at this problem.

  • I really, REALLY encourage you not to use list as a variable name. This causes headaches.
  • Your l_gcd function will do better to initialize to the first element of the list, for clarity. reduce from functools would be a good option to use for the gcd of a list (but see below, you should do this differently).
  • I think your idea is to find the gcd of the list with one value excluded each time, but that requires handling N^2 gcd operations which will give you the TLE result. You need to accumulate gcds from both ends to avoid this
  • Your runtime error probably comes from the N=1 case, try input:
1
1
5

There is a small typo in the second sentence of the second bullet point in “QUICK EXPLANATION” section. It should be “notes” instead of “nodes”.

Thanks for the editorial BTW!

My code is giving TLE, what am I doing wrong Solution: 48641143 | CodeChef

for i in range(n): # O(N) loop
    if i==0:
        x=b[n-2]
    elif i==n-1:
        x=f[n-2]
    else:
        x=math.gcd(f[i-1],b[n-2-i])
    ans = int(min(ans,(sum(A)-A[i]+x)/x)) # O(N) for sum

# Overall time complexity: O(N * N)

Hence, TLE.

1 Like