Need suggestion to get the most optimal solution


#1

Can anyone suggest me to optimize the solution to get reduce time complexity for the solution?


vector Solution::solve(vector &A, vector &B) {
//1.Generate subarrays of A
//2.Take the maximum element from each subarray of A and insert it into a new array G.
vector G;
int max=0;
int l1=A.size();
// int l2=B.size();
//cout<<“A.size=”<<l1<<endl;
for(int i=0;i<l1;i++)
{
for(int j=i;j<l1;j++)
{
// cout<<A[i][j];
max=0;
for(int k=i;k<=j;k++)
{
if(max<A[k])
{
max=A[k];
}}
G.push_back(max);
}}
//.Print the content of G

int Sg=G.size();
// cout<<"Sg="<<Sg<<endl;
// for(int i=0;i<Sg;i++)
// {
//  //   cout<<G[i]<<endl;
// }

//3. To find the divisor of the number

int item1;
vector Divisor;

for(int i=0;i<Sg;i++)
{
for(int j=1;j<=G[i];j++)
{
if(G[i]%j==0)
{
Divisor.push_back(j);
}
}
//Replace every element of G with the product of their divisors mod 1e9 + 7.

int temp=Divisor.size();

//cout<<“Divisor size=”<<temp<<endl;
long long int c=1;
for(int i=0;i<temp;i++)
{
c=c*Divisor[i];
}
Divisor.clear();
c=c%1000000007;
// G.clear();
G[i]=c;
//G.push_back©;
//c=1;
// cout<<“c=”<<c<<endl;
// c=1;
}
//To check the content of the Divisor vector
int l3=Divisor.size();

for(int i=0;i<l3;i++)
{
cout<<Divisor[i]<<" "<<endl;
}

//sort G in descending order

sort(G.begin(),G.end(),greater());

//In each query, you are given an integer K, where you have to find the Kth element in G.

int bsize=B.size();

for(int i=0;i<bsize;i++)
{
B[i]=B[i]-1;
}

//Get the element at that index
vector G2;
for(int i=0;i<bsize;i++)
{
G[i]=G[B[i]];
// G.push_back(G[B[i]]);
}

return G;
}


#2

I did almost same as yours. Do you have optimal answer now?


#3

Not yet @SysSn13 if i will come up, then will share here in the same thread.


#4

Have a look, many elements could be removed. One loop could be reduced in the sub array part itself. Still not the most optimized but better off !

vector<int> Solution::solve(vector<int> &A, vector<int> &B) {

vector<int> G;
int max=0, i, j, l=A.size();

for(i=0;i<l;i++)
{
    max=0;
    for(j=i;j<l;j++)
    {
        if(A[j]>max)    max=A[j];
        G.push_back(max);
    }
}

for(i=0;i<G.size();i++)
{
    long long int c=1;
    for(j=1;j<=G[i];j++)    if(G[i]%j==0)   c = c*j%1000000007;
    c=c%1000000007;
    G[i]=c;
}

sort(G.begin(),G.end(),greater());

vector<int> G2;
for(int i=0;i<B.size();i++)     G2.push_back(G[B[i]-1]);

return G2;
}